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.
翻译:在随机排序模型中,我们研究了在线设施定位问题与统一设施成本的随机排序模式。 Meyerson的算法[FOCS'01]可以说是这一问题的最自然和最简单的在线算法,具有若干优势和吸引力。随机排序模型中的分析是随机排序分析的基石之一,超出了秘书问题的范围。 Meyerson的算法在标准最差情况对抗排序模型中被证明(暂时)是最佳的,在随机排序模型中具有8美元的竞争力。尽管随机排序模型中这种约束是长期存在的先进技术,但并不为人所知,而且Meyerson算法的真正竞争性拉皮奥仍然是超过20年的开放问题。我们解决这个问题,并证明Myerson算法的竞争性拉皮卡在随机排序模型中是(暂时的)最严格的,表明它完全具有4美元的竞争力。在我们进行严格分析之后,我们引入了通用的、具有可靠性的Myerson算法是所有原始版本的优势的参数化版本。我们显示,这个家族中最好的竞争性算法是3美元,我们最后能够证明这个家族的竞争性的另外一种2美元。