Lune

SODA2023Top-tier venue

Almost Tight Bounds for Online Facility Location in the Random-Order Model

Haim Kaplan, David Naori, Danny Raz

Abstract

We study the online facility location problem with uniform facility costs in the random-order model. Meyerson's algorithm [FOCS'01] is arguably the most natural and simple online algorithm for the problem with several advantages and appealing properties. Its analysis in the random-order model is one of the cornerstones of random-order analysis beyond the secretary problem. Meyerson's algorithm was shown to be (asymptotically) optimal in the standard worst-case adversarial-order model and 8-competitive in the random order model. While this bound in the random-order model is the long-standing state-of-the-art, it is not known to be tight, and the true competitive-ratio of Meyerson's algorithm remained an open question for more than two decades. We resolve this question and prove tight bounds on the competitive-ratio of Meyerson's algorithm in the random-order model, showing that it is exactly 4-competitive. Following our tight analysis, we introduce a generic parameterized version of Meyerson's algorithm that retains all the advantages of the original version. We show that the best algorithm in this family is exactly 3-competitive. On the other hand, we show that no online algorithm for this problem can achieve a competitive-ratio better than 2. Finally, we prove that the algorithms in this family are robust to partial adversarial arrival orders.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Improved Bounds for Online Facility Location with Predictions cites Online Graph Algorithms with Predictions
  • Improved Bounds for Online Facility Location with Predictions cites Online Facility Location with Multiple Advice
  • Improved Bounds for Online Facility Location with Predictions cites Online Facility Location with Predictions
  • Online Facility Location with Multiple Advice cites Online Facility Location with Predictions
  • Online Facility Location with Predictions cites Online Facility Location with Multiple Advice
  • Set Covering with Our Eyes Wide Shut cites Competitive Analysis with a Sample and the Secretary Problem
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Low-Distortion Clustering with Ordinal and Limited Cardinal InformationJakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Matteo Russo et al.AAAI 2024 · 8 citations
  2. Online Decision Making with Generative Action SetsJianyu Xu, Vidhi Jain, Bryan Wilder, Aarti SinghICLR 2026 · 3 citations
  3. Set Covering with Our Eyes Wide ShutAnupam Gupta, Gregory Kehne, Roie LevinSODA 2024 · 3 citations

Builds on9

  1. Online Facility Location with Multiple AdviceMatteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi et al.NeurIPS 2021 · 45 citations
  2. Online Facility Location with PredictionsShaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang et al.ICLR 2022 · 34 citations
  3. Competitive Analysis with a Sample and the Secretary ProblemHaim Kaplan, David Naori, Danny RazSODA 2020 · 26 citations
  4. Online Graph Algorithms with PredictionsYossi Azar, Debmalya Panigrahi, Noam TouitouSODA 2022 · 23 citations
  5. Improved Bounds for Online Facility Location with PredictionsDimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis, Nikolas Patris et al.AAAI 2025 · 16 citations

Related papers

  1. Stronger adversaries grow cheaper forests: online node-weighted Steiner problemsSander Borst, Marek Eliás, Moritz VenzinSODA 2025 · 1 citation
  2. Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online OptimumEnze Sun, Zhihao Gavin Tang, Yifan WangSTOC 2025 · 1 citation
  3. Online Rounding and Learning Augmented Algorithms for Facility LocationSilvio Lattanzi, Debmalya Panigrahi, Ola SvenssonICLR 2026
  4. A Deterministic Polylogarithmic Competitive Algorithm for Matching with DelaysMarc Dufay, Roger WattenhoferSODA 2026
  5. Dynamic High-Dimensional Facility Location with Low RecourseSayan Bhattacharya, Martín Costa, Silvio Lattanzi, Jakub Łącki et al.ICML 2026
Dusk over the sea between two cliffs drawn in fine vertical lines