论文标题
随机订单模型中在线设施位置的几乎紧密界限
Almost Tight Bounds for Online Facility Location in the Random-Order Model
论文作者
论文摘要
我们在随机订单模型中研究了在线设施位置问题，其设施成本均匀。 Meyerson的算法[FOCS'01]可以说是具有几种优势和吸引人属性的问题最自然和最简单的在线算法。它在随机阶模型中的分析是秘书问题以外的随机分析的基石之一。在标准最差的对抗阶模型中，梅耶森的算法（渐近）在随机订单模型中是最佳的。虽然在随机级模型中的这种绑定是长期以来的最新最新，但众所周知，梅耶森算法的真正竞争性比例是二十年来一直是一个悬而未决的问题。 我们解决了这个问题，并证明了随机级模型中Meyerson算法的竞争比率的紧密界限，这表明它恰好是$ 4 $竞争。经过严格的分析，我们引入了Meyerson算法的一般参数化版本，该版本保留了原始版本的所有优点。我们表明，这个家庭中最好的算法恰好是$ 3 $竞争。另一方面，我们表明，对于此问题，没有在线算法可以更好地获得比$ 2 $的竞争比率。最后，我们证明该家族中的算法对部分对立的到达命令具有鲁棒性。
We study the online facility location problem with uniform facility costs in the random-order model. Meyerson's algorithm [FOCS'01] is arguably the most natural and simple online algorithm for the problem with several advantages and appealing properties. Its analysis in the random-order model is one of the cornerstones of random-order analysis beyond the secretary problem. Meyerson's algorithm was shown to be (asymptotically) optimal in the standard worst-case adversarial-order model and $8$-competitive in the random order model. While this bound in the random-order model is the long-standing state-of-the-art, it is not known to be tight, and the true competitive-ratio of Meyerson's algorithm remained an open question for more than two decades. We resolve this question and prove tight bounds on the competitive-ratio of Meyerson's algorithm in the random-order model, showing that it is exactly $4$-competitive. Following our tight analysis, we introduce a generic parameterized version of Meyerson's algorithm that retains all the advantages of the original version. We show that the best algorithm in this family is exactly $3$-competitive. On the other hand, we show that no online algorithm for this problem can achieve a competitive-ratio better than $2$. Finally, we prove that the algorithms in this family are robust to partial adversarial arrival orders.
