2026/07/24 by Bo Peng, Zhihao Gavin Tang
#cs.DS #cs.GT
We study online metric facility location in the random-order model with arbitrary positive opening costs. A finite set of candidate facilities and their costs is known in advance, while an adversary fixes a multiset of demand points that arrives in a uniformly random order. This setting includes both prescribed candidate sites and the classical finite full-space node-cost model. For a known horizon, we give a deterministic 4.2674-competitive algorithm, improving the previous factor 33 for nonuniform opening costs. At rank t, the algorithm uses the positive normalized rank qt=t/n, chooses a candidate minimizing d(x,y)+λt fy, where λt=min\1,qt/μ\, and opens it when the current connection distance covers this penalized objective. The analysis uses a monotone one-round charge and an upper-envelope decomposition to control later points and the first point of each optimal cluster. With unit opening costs, the rule reduces exactly to a cutoff on the distance improvement attainable from a nearest candidate. A supplementary appendix gives the sharper analysis of the closely related zero-start rank cutoff and obtains a ratio below 3.2805. We also prove a 3-o(1) lower bound for arbitrary randomized online algorithms. The lower bound already holds with uniform costs on a prescribed candidate set and transfers, without loss, to the finite full-space model with nonuniform opening costs. Together with the recent competitive ratio below 2.42 for full-space uniform costs, this yields a strict separation between the full-space uniform- and nonuniform-cost models.