Pith. sign in

REVIEW 4 minor 1 cited by

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

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Using a request's arrival time as density evidence breaks the long-standing 3-competitive barrier for random-order online facility location, down to below 2.42 deterministically.

desk verdict Clean break of the 3-barrier for random-order facility location via arrival-time density, with matching family lower bounds and a first constant-competitive deterministic algorithm. read the letter →

arxiv 2607.10564 v1 pith:MQIQVD6T submitted 2026-07-12 cs.DS

Yichen Huang , Shaofeng H.-C. Jiang This is my paper · ORCID
classification cs.DS MSC 68W2768W4090C27
keywords onlinefacilitylocationrandom-ordermodelcompetitiveanalysisarrivaltimeDistProbmetric
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Online facility location asks an algorithm to open facilities and connect arriving clients on the fly, paying both opening and distance costs. In the random-order model the clients arrive in a random permutation, yet the best prior guarantee was still only 3-competitive, matching a known barrier for every algorithm that ignores time. This paper shows that the arrival clock itself carries geometric density information: dense regions reveal themselves early, sparse ones late. By folding that clock into the opening rule the authors obtain two improved algorithms. One is deterministic and achieves a competitive ratio below 2.42; the other is randomized, stays under 2.59 in random order, and simultaneously keeps the optimal logarithmic guarantee against adversarial order. The concrete rules are simple cut-offs or two-phase multipliers, yet the analyses prove that time is indispensable: any rule that ignores it cannot beat 3.

What carries the argument

The TimeDist family, realized by the deterministic μ-DistCut rule that opens when distance ≥ min{1, z_t / μ} (z_t = (t-1)/n), together with the analysis that anchors every offline cluster at its first-arriving request and balances the resulting opening-versus-connection trade-off; and the qt-DistProb family whose balanced-opening pivot and geometry-free relaxed excess process reduce the time-varying analysis to a scalar functional ρ(q).

What would settle it

Compute or simulate the exact competitive ratio of μ-DistCut (or of the optimized two-phase qt sequence) on large random-order instances drawn from the sparse-star and dense-location hard distributions used in the lower-bound proofs; if either ratio exceeds the claimed constants, the corresponding upper bound is false.

Watch

Extended reading notes

Core claim

The paper establishes that algorithms whose opening decisions may depend on both current distance and arrival time strictly improve upon the classical DistProb family. Concretely, a deterministic threshold rule that opens a request when its distance exceeds a linear function of its normalized arrival time is at most 2.42-competitive in random order, while a time-varying DistProb rule with a two-phase multiplier sequence is at most 2.59-competitive in random order and still O(log n / log log n)-competitive against adversarial order.

Load-bearing premise

The analysis of the time-varying algorithm treats the adaptive distances after each failed opening as if an adversary could shrink them arbitrarily; if that worst-case relaxation is too loose the concrete 2.59 ratio may overstate the true cost.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies online metric facility location with uniform opening costs in the random-order model. It breaks the previous 3-competitive barrier of the q-DistProb family by introducing algorithms that use arrival time. The first is a deterministic μ-DistCut rule (open if d(v_t,F)≥min{1,z_t/μ}) that is at most max{1+e^{-(1+μ)/μ},2(1+μ)}<2.42-competitive (Theorem 3.1). The second is a time-varying q_t-DistProb algorithm with a two-phase schedule that is <2.59-competitive in random order while remaining O(log n/log log n)-competitive in adversarial order (Theorems 4.1 and 1.2). Matching lower bounds are given for time-oblivious request-local rules (3), the q_t-DistProb family (≈2.519), and the TimeDist family (≈2.42).

Significance. The work closes a substantial fraction of the long-standing 2-to-3 gap for random-order online facility location and supplies the first constant-competitive deterministic algorithm in this model. The arrival-time idea is cleanly motivated and yields two simple, efficiently implementable algorithms. Full self-contained proofs are given for both upper bounds (first-arrival anchor for DistCut; balanced-opening pivot, relaxed excess process and equalization for q_t-DistProb) and for three matching lower bounds; free parameters are optimized against the paper’s own analytic bounds rather than fitted externally. The dual-guarantee algorithm that retains the optimal adversarial-order ratio is especially valuable for the literature.

minor comments (4)
  1. The concrete numerical values 2.42 and 2.59 appear only after optimizing μ* and α*; stating the exact transcendental equations solved for these constants already in the introduction (or in a short table) would make the claims easier to verify without recomputing.
  2. Notation for center excess a_t(u)=(D_t-r_u)+ and the balanced-opening coupling is introduced gradually across Section 4.1; a short formal definition block at the start of that subsection would improve readability.
  3. Appendix A shows an Ω(√n) adversarial lower bound for DistCut; a one-sentence pointer to this fact already in the introduction (where the loss of adversarial robustness is mentioned) would be helpful.
  4. A few minor typos appear (e.g., “DistCutadmits” missing space, occasional missing punctuation after display equations). A light copy-edit pass would clean them.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: competitive ratios are derived from self-contained first-principles analyses of two algorithmic families; free parameters only minimize the paper's own proven upper bounds.

full rationale

The paper's central claims (Theorems 1.1/3.1 and 1.2/4.1) are pure competitive-analysis upper bounds proved from scratch under the standard random-order model. For μ-DistCut the chain is first-arrival anchor (Lemma 3.2) → cluster decomposition (Lemma 3.3) → first-anchor tradeoff via random-order tail bounds (Lemma 3.4) → max{1+e^{-(1+μ)/μ}, 2(1+μ)}; μ* is chosen only to balance that already-proved expression. For qt-DistProb the chain is balanced-opening cost decomposition (Lemma 4.8) → geometry-free relaxed process domination (Lemma 4.11) → equalization to the scalar ρ(q) (Lemma 4.13) → optimization over nonincreasing sequences, with a two-phase front-loaded sequence shown extremal (Claim 4.15 / Corollary 4.2). Neither ratio is obtained by fitting external data, renaming a known empirical pattern, or importing a uniqueness theorem from overlapping authors. Prior citations (Meyerson, KNR23, Fotakis) supply context and the classical adversarial-order scale argument that is adapted, not load-bearing for the new random-order ratios. Matching family lower bounds (Theorems 5.1–5.3) further confirm the claims are not definitional tautologies. Score 0 is therefore appropriate.

Assumptions & free parameters 3 free parameters · 4 assumptions · 4 invented entities

The work rests on the classical random-order online facility-location model (uniform opening cost scaled to 1, metric space, irrevocable decisions) plus two free parameters that are optimized against the paper’s own analytic bounds. No external data or unproved physical hypotheses are used. The invented algorithmic families and the balanced-opening / center-excess notions are definitional tools internal to the proofs.

free parameters (3)
  • μ (DistCut cutoff) = ≈0.21
    Chosen to balance 1+e^{-(1+μ)/μ} against 2(1+μ); the optimizing value ≈0.21 yields the stated 2.42 ratio.
  • α* (qt front-loaded threshold) = ≈0.293
    Fraction of the sequence on which qt=1; solved from ((1-α)/α)exp(-1/(1-α))=2α to minimize the analytic upper bound, giving ≈0.293 and ratio ≈2.586.
  • ε (adversarial-robustness floor) = arbitrary small positive constant
    Positive constant added to late qt values so that the sequence stays bounded away from zero; increases the random-order ratio by O(ε) while restoring the O(log n/log log n) adversarial guarantee.
assumptions (4)
  • domain assumption Requests arrive in uniformly random order (random-order model of Meyerson).
    Used throughout Sections 3–4; the DistCut algorithm is shown separately to have Ω(√n) ratio under adversarial order.
  • standard math Facility opening cost may be scaled to 1 without loss of generality.
    Standard homogeneity argument stated in the preliminaries.
  • domain assumption The algorithm may open facilities only at request locations (request-local).
    Explicitly assumed for all lower bounds in Section 5; upper-bound algorithms also obey it.
  • standard math Triangle inequality of the underlying metric.
    Invoked repeatedly for radius charges and center-excess bounds.
invented entities (4)
  • TimeDist family / μ-DistCut
    purpose: Deterministic opening rule that depends on both arrival time and distance; realizes the 2.42 ratio.
    Defined by the cutoff inequality (3); shown optimal inside the TimeDist family by a matching lower bound.
  • qt-DistProb family
    purpose: Time-varying generalization of classical DistProb that retains adversarial-order robustness.
    Defined by the opening probability (2)/(4); analysis yields the 2.59 ratio.
  • Balanced opening / center excess at(u)=(Dt-ru)+
    purpose: Analytic pivot that biases the first opening toward the offline center while remaining coupled to actual openings.
    Introduced in Section 4.1; essential for the varying-qt decomposition.
  • Relaxed excess process and functional ρ(q)
    purpose: Geometry-free upper bound on the center-excess waiting cost HC.
    Definition 4.10 and Lemma 4.13 reduce the adaptive metric process to a scalar optimization.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Power of Arrival Times in Random-Order Online Facility Location." pith.science (2026). https://pith.science/paper/MQIQVD6T

@misc{pith2026260710564,
  author       = {Pith},
  title        = {Pith review of: The Power of Arrival Times in Random-Order Online Facility Location},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MQIQVD6T}},
  note         = {Machine review of arXiv:2607.10564}
}
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Random-Order Online Facility Location Beyond Uniform Opening Costs

    cs.DS 2026-07 accept novelty 8.0 of 10

    A rank-based penalized-distance algorithm is 4.2674-competitive for random-order facility location with arbitrary opening costs, and a 3-o(1) lower bound separates uniform- and nonuniform-cost models.

Reference graph

Works this paper leans on

13 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    A Simple and Deterministic Competitive Algorithm for Online Facility Location

    [ABUV04] Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. “A Simple and Deterministic Competitive Algorithm for Online Facility Location”. In:Informa- tion and Computation194.2 (2004), pp. 175–202. [ACL+21] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. “Online Facility Location with M...

    2004

  2. [2]

    Curran Associates, Inc., 2021, pp. 4661–

    2021

  3. [3]

    Improved Online Algorithms for Knapsack and GAP in the Random Order Model

    Curran Associates, Inc., 2022, pp. 13852–13863. [AKL21] Susanne Albers, Arindam Khan, and Leon Ladewig. “Improved Online Algorithms for Knapsack and GAP in the Random Order Model”. In:Algorithmica83.6 (2021), pp. 1750–1785. [APT22] Yossi Azar, Debmalya Panigrahi, and Noam Touitou. “Online Graph Algorithms with Predictions”. In:Proceedings of the 2022 Annu...

    2022

  4. [4]

    Online Edge Coloring Al- gorithms via the Nibble Method

    [BGW21] Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. “Online Edge Coloring Al- gorithms via the Nibble Method”. In:Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2021, pp. 2830–2842. [BMM12] Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani. “Online Graph Edge- Coloring i...

    2021

  5. [5]

    Improved Combinatorial Algorithms for Facility Location Problems

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2018, 21:1–21:15. [CG05] Moses Charikar and Sudipto Guha. “Improved Combinatorial Algorithms for Facility Location Problems”. In:SIAM J. Comput.34.4 (2005), pp. 803–824. [CMRS64] Yuan Shih Chow, Sigeiti Moriguti, Herbert Robbins, and Stephen M. S...

    2018

  6. [6]

    Who Solved the Secretary Problem?

    [Fer89] Thomas S. Ferguson. “Who Solved the Secretary Problem?” In:Statistical Science 4.3 (1989), pp. 282–289. [FGG+25] Dimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis, Nikolas Patris, and Thanos Tolias. “Improved Bounds for Online Facility Location with Predictions”. In:Proceedings of the AAAI Conference on Artificial Intelligence. Vol

    1989

  7. [7]

    On the Competitive Ratio for Online Facility Location

    2025, pp. 26973–26981. [Fot03] Dimitris Fotakis. “On the Competitive Ratio for Online Facility Location”. In:Au- tomata, Languages and Programming (ICALP 2003). Vol

    2025

  8. [8]

    A Primal-Dual Algorithm for Online Non-Uniform Facility Loca- tion

    Lecture Notes in Computer Science. Springer, 2003, pp. 637–652. [Fot07] Dimitris Fotakis. “A Primal-Dual Algorithm for Online Non-Uniform Facility Loca- tion”. In:Journal of Discrete Algorithms5.1 (2007), pp. 141–148. [Fot11a] Dimitris Fotakis. “Memoryless facility location in one pass”. In:ACM Trans. Algo- rithms7.4 (Sept. 2011). [Fot11b] Dimitris Fotaki...

    2003

Show all 13 references
  1. [9]

    Random-Order Models

    Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020, 42:1–42:23. [GS21] Anupam Gupta and Sahil Singla. “Random-Order Models”. In:Beyond the Worst- Case Analysis of Algorithms. Ed. by Tim Roughgarden. Cambridge Unive...

    2020

  2. [10]

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

    arXiv:2110.08840 [cs.DS]. [KNR23] Haim Kaplan, David Naori, and Danny Raz. “Almost Tight Bounds for Online Fa- cility Location in the Random-Order Model”. In:Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2023, pp. 1523–1544. eprint: https://e...

    2023 doi arXiv

  3. [11]

    Primal Beats Dual on Online Packing LPs in the Random-Order Model

    Lecture Notes in Computer Science. Springer, 2013, pp. 589–600. [KRTV18] Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and Berthold V¨ ocking. “Primal Beats Dual on Online Packing LPs in the Random-Order Model”. In:SIAM Journal on Computing47.5 (2018), pp. 1939–1964. [Lan1...

    2013

  4. [12]

    Improved Approximation Al- gorithms for Metric Facility Location Problems

    [MYZ02] Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. “Improved Approximation Al- gorithms for Metric Facility Location Problems”. In:Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002, Proceedin...

    2002

  5. [13]

    Offline and Online Facility Leasing

    Lecture Notes in Computer Science. Springer, 2002, pp. 229–242. [NW13] Chandrashekhar Nagarajan and David P. Williamson. “Offline and Online Facility Leasing”. In:Discrete Optimization10.4 (2013), pp. 361–370. [Rou21] Tim Roughgarden, ed.Beyond the Worst-Case Analysis of Algor...

    2002

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.