论文标题
在线设施分配问题的新结果和界限
New Results and Bounds on Online Facility Assignment Problem
论文作者
论文摘要
考虑一个在线设施分配问题，其中一组设施$ f = \ {f_1，f_2，f_2，f_3，\ cdots，f_ {| f |} \} $等于容量$ l $的$位于公制空间上，客户在该空间上以在线方式以一个在线方式到达。在新客户$ C_ {i+1} $到达之前，我们将客户$ C_I $分配给设施$ f_j $。此任务的成本是$ C_I $和$ f_j $之间的距离。这个问题的目的是最大程度地减少所有任务成本的总和。最近，艾哈迈德（Ahmed）等人。 （TCS，806，pp。455-467，2020）研究了设施位于线路上的设施并计算出“算法贪婪”的竞争比率，该比例将客户分配给最近的可用设施。他们计算了名为“算法最佳填充”算法的竞争比率，该算法分配了新客户，考虑到所有以前的客户的最佳分配。他们还研究了设施位于连接的未加权图上的问题。 在本文中，我们首先考虑$ f $位于连接的未加权网格图$ g $ size $ r \ times c $的顶点，客户一个在$ g $的顶点上有一个位置。我们表明，算法贪婪具有竞争性比率$ r \ times c + r + c $，算法Optimal-fill具有竞争性比率$ o（r \ times c）$。后来，我们表明，对于任何任意图，算法最佳填充的竞争比率为$ 2 | f | $。我们的界限比以前的结果更紧密，更好。我们还认为设施是任意分布在飞机上的，并为场景提供了算法。我们还提供了具有竞争比率$（2N-1）$的算法。最后，我们考虑了一个直线度量空间，并表明在线设施分配问题的算法比率不到$ 9.001 $。
Consider an online facility assignment problem where a set of facilities $F = \{ f_1, f_2, f_3, \cdots, f_{|F|} \}$ of equal capacity $l$ is situated on a metric space and customers arrive one by one in an online manner on that space. We assign a customer $c_i$ to a facility $f_j$ before a new customer $c_{i+1}$ arrives. The cost of this assignment is the distance between $c_i$ and $f_j$. The objective of this problem is to minimize the sum of all assignment costs. Recently Ahmed et al. (TCS, 806, pp. 455-467, 2020) studied the problem where the facilities are situated on a line and computed competitive ratio of "Algorithm Greedy" which assigns the customer to the nearest available facility. They computed competitive ratio of algorithm named "Algorithm Optimal-Fill" which assigns the new customer considering optimal assignment of all previous customers. They also studied the problem where the facilities are situated on a connected unweighted graph. In this paper we first consider that $F$ is situated on the vertices of a connected unweighted grid graph $G$ of size $r \times c$ and customers arrive one by one having positions on the vertices of $G$. We show that Algorithm Greedy has competitive ratio $r \times c + r + c$ and Algorithm Optimal-Fill has competitive ratio $O(r \times c)$. We later show that the competitive ratio of Algorithm Optimal-Fill is $2|F|$ for any arbitrary graph. Our bound is tight and better than the previous result. We also consider the facilities are distributed arbitrarily on a plane and provide an algorithm for the scenario. We also provide an algorithm that has competitive ratio $(2n-1)$. Finally, we consider a straight line metric space and show that no algorithm for the online facility assignment problem has competitive ratio less than $9.001$.
