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. In this setting, we present a deterministic $4.2674$-competitive algorithm for a known horizon, improving the previous factor of $33$ for nonuniform opening costs. At rank $t$, the algorithm uses the positive normalized rank $q_t=t/n$, choosing a candidate that minimizes $d(x,y)+\lambda_t f_y$, where $\lambda_t=\min\left\{1,\frac{q_t}{\mu}\right\}$ and opens it when the current connection distance covers this penalized objective. The analysis employs 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 simplifies to a cutoff on the distance improvement attainable from the nearest candidate. A supplementary appendix provides sharper analysis of the closely related zero-start rank cutoff, achieving a ratio below $3.2805$. We also prove a $3-o(1)$ lower bound for arbitrary randomized online algorithms. This lower bound 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.
Blogger's Review: This paper significantly enhances the efficiency of online facility location algorithms by introducing a random-order model, particularly in scenarios with nonuniform opening costs, demonstrating an improved competitive ratio. It provides new insights for future algorithm design and highlights the fundamental differences between uniform and nonuniform cost models, warranting further research and exploration.