{"ID":6536121,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10564","arxiv_id":"2607.10564","title":"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.","short_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...","url_abs":"https://arxiv.org/abs/2607.10564","url_pdf":"https://arxiv.org/pdf/2607.10564v1","authors":"[\"Yichen Huang\",\"Shaofeng H. -C. Jiang\"]","published":"2026-07-12T04:42:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}