Random-Order Online Facility Location Beyond Uniform Opening Costs
2026-07-24 • Data Structures and Algorithms
Data Structures and AlgorithmsComputer Science and Game Theory
AI summaryⓘ
The authors study a problem where facilities with different opening costs must serve customers arriving in random order, aiming to open facilities and connect customers cost-effectively. They propose a new deterministic algorithm that improves previous performance guarantees significantly, achieving a competitive ratio of about 4.27. Their approach uses a rule based on the position of each arriving customer and a balance between connection distance and facility cost. They also prove a lower bound showing no randomized online algorithm can do much better than a factor of 3, highlighting differences between uniform and nonuniform cost models.
Online algorithmsMetric facility locationCompetitive ratioRandom-order modelNonuniform opening costsDeterministic algorithmLower boundFacility opening costConnection distanceFinite candidate sites
Authors
Bo Peng, Zhihao Gavin Tang
Abstract
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 $q_t=t/n$, chooses a candidate minimizing $d(x,y)+λ_t f_y$, where $λ_t=\min\{1,q_t/μ\}$, 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.