The Power of Arrival Times in Random-Order Online Facility Location

Abstract

We study online metric facility location with uniform opening costs in the random-order model (Meyerson FOCS'01). The best previous upper bound was a $3$-competitive randomized algorithm (Kaplan, Naori, Raz SODA'23), leaving a gap to the best known lower bound of $2$. In this work, we give two algorithms with improved competitive ratios: (i) a deterministic algorithm with a competitive ratio below $2.42$ and (ii) a randomized algorithm with a competitive ratio below $2.59$ and the additional property that it retains the asymptotically optimal $O(\log n/\log \log n)$ competitive ratio in the adversarial-order model. A key improvement is to take the arrival time of the request into consideration when making opening decisions: The arrival time carries geometric information about the local density around the request, which fundamentally helps the algorithm.