Pith. sign in

REVIEW 3 minor 30 references

Random-Order Online Facility Location Beyond Uniform Opening Costs

T0 review · 0 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read One rank-aware comparison of penalized distances yields a deterministic 4.2674-competitive algorithm for random-order online facility location with arbitrary positive opening costs, and a 3-o(1) lower bound separates uniform from nonuniform

desk verdict A real improvement in random-order facility location: nonuniform opening costs cut from 33 to 4.2674, plus a 3-o(1) lower bound and a clean uniform/nonuniform separation — worth a serious referee. read the letter →

arxiv 2607.22496 v1 pith:T7YJUNAL submitted 2026-07-24 cs.DS cs.GT

Bo Peng , Zhihao Gavin Tang This is my paper · ORCID
classification cs.DScs.GT MSC 68W2790B8068W40
keywords onlinefacilitylocationrandom-ordermodelcompetitiverationonuniformopeningcostsrank-basedalgorithmmetriclowerboundprescribedcandidatesites
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

The paper studies online metric facility location when an adversary fixes the multiset of demands but they arrive in uniformly random order, and opening costs may differ across candidate sites. Its main claim is a deterministic, polynomial-time algorithm that is 4.2674-competitive whenever the number of requests is known in advance, improving the previous factor of 33 for nonuniform costs. The algorithm compares each arriving point against all candidates through a penalized distance—connection distance plus a rank-discounted opening cost—and opens at most one facility when the current connection distance covers that value. The paper also proves that no randomized algorithm can do better than 3-o(1) even with uniform costs on a prescribed candidate set, and transfers this lower bound to the full-space nonuniform-cost model. Together with a known sub-2.42 result for full-space uniform costs, this yields a strict separation between uniform- and nonuniform-cost versions.

What carries the argument

The central object is a rank-discounted penalized distance: at rank t with normalized rank q_t=t/n, each candidate y is scored as d(x,y)+λ_t f_y with λ_t=min{1,q_t/μ}; the algorithm opens the minimizer only if the current connection distance is at least this score. The proof's load-bearing tools are a monotone one-round charge, which lets histories be replaced by distances through the first point of an optimal cluster, and an upper-envelope decomposition, which charges the selected candidate's excess in one coordinate increment at a time using random-order rank estimates.

What would settle it

For the upper bound: exhibit a metric, candidate set, positive opening costs, and fixed n-demand multiset for which Penalized-Distance RankCut with μ=0.31684 has expected cost exceeding 4.2674·OPT; a violation would appear at a single optimal cluster where the claimed Ψ(μ)-on-opening plus (3+4μ)-on-connection bound fails. For the lower bound: give a randomized algorithm whose expected ratio on the paper's N-location support-hiding instance is below 3N/(N+3) for arbitrarily large N, contradicting Theorem 5.1.

Watch

Extended reading notes

Core claim

Penalized-Distance RankCut is the paper's algorithm. At the t-th arrival it sets λ_t = min{1, t/(μn)} and selects the candidate y minimizing d(x,y) + λ_t f_y, opening y when the current connection distance D satisfies D ≥ d(x,y)+λ_t f_y. The analysis fixes an optimal solution, clusters demands around its facilities, and bounds each cluster's expected online cost by Ψ(μ) times the cluster's opening cost plus (3+4μ) times its connection cost; balancing the two coefficients at μ≈0.31684 yields E[ALG] < 4.2674·OPT for every fixed demand multiset. The lower-bound construction gives a 3-o(1) factor for arbitrary randomized algorithms, even with uniform costs on a prescribed candidate set, and a re

Load-bearing premise

The 4.2674 upper bound is conditional on the total number of requests n being revealed to the algorithm in advance; without that horizon, the rank clock q_t=t/n cannot be formed and the paper explicitly does not claim the same guarantee.

Editorial extensions

If this is right

  • For any fixed demand multiset of size n, with the horizon known and arbitrary positive opening costs, the algorithm is deterministic, polynomial-time, and satisfies E[ALG] < 4.2674·OPT, improving the previous factor 33.
  • With unit opening costs, the rule collapses to a nearest-candidate cutoff on the attainable distance improvement, and the zero-start variant is analyzed to give a ratio below 3.2805.
  • The 3-o(1) lower bound holds for every randomized algorithm, even when the horizon is revealed and even with uniform costs on a prescribed candidate set.
  • The same lower bound transfers to the full-space nonuniform model, so no algorithm can beat 3 there; combined with a sub-2.42 upper bound for full-space uniform costs, the optimal ratios of the two models are strictly different.
  • Any future improvement below 3 must exploit instances whose offline optimum uses a genuinely hidden multi-facility structure, since one-facility hidden-center benchmarks stop at three.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural testable extension is whether the rank clock can be replaced by a doubling or horizon-estimation scheme while retaining a constant near 4.2674; the paper's own discussion notes that a direct doubling argument does not preserve the analysis.
  • The separation result suggests the hardness comes from cost heterogeneity rather than from restricting which points can serve as facilities: making every point feasible but costs nonuniform keeps the 3 barrier.
  • If the 3+4μ coefficient is slack, attempting to certify a smaller coefficient on adversarial cluster examples could tighten the constant without changing the algorithm.
  • The support-hiding lower bound invites a sample-based variant: an algorithm that sees a small random sample of the demand multiset before opening may bypass the 3 barrier, a setting the paper does not address.
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 / 3 minor

Summary. This paper studies random-order online metric facility location with a known finite candidate set and arbitrary positive opening costs, under the additional assumption that the horizon n is known. The main result is a deterministic polynomial-time algorithm, Penalized-Distance RankCut, with competitive ratio below 4.2674, improving the previous factor 33 for nonuniform opening costs. The analysis fixes an optimal solution and bounds each optimal cluster using a monotone one-round charge, a linear-penalty upper-envelope decomposition, and a rank-tail certificate for the first point of the cluster. The paper also proves a 3-o(1) lower bound for arbitrary randomized online algorithms, first in the prescribed-candidate uniform-cost model and then transferred to the full-space nonuniform-cost model. Together with the cited sub-2.42 uniform-cost upper bound of Huang and Jiang, this yields a strict separation between the uniform and nonuniform full-space models. A supplementary appendix gives a sharper 3.2805 bound for the unit-cost prescribed-candidate case.

Significance. If correct, these results are significant. The 4.2674 upper bound is a large improvement over the previous 33, and the algorithm is deterministic, rank-based, and runs in O(|F|) time per request. The 3-o(1) lower bound is clean, self-contained, and appears to hold for every randomized algorithm even when the horizon is revealed. The transfer from prescribed candidates to the full-space nonuniform model is elegant and makes the lower bound independent of forbidden sites. The proofs are modular and checkable: the cluster bookkeeping in Section 4.2 is exact, the envelope lemma is stated with careful tie handling, and the i.i.d.-to-random-order conditioning argument in Section 5.3 is correct. The known-horizon limitation is explicitly scoped in Remark 2.1 and Section 6 and does not undermine the stated claims. The free parameter mu is chosen analytically at the intersection of the two coefficient curves, not tuned to the constant. The main external dependency is the cited [HJ26] sub-2.42 bound used only in Corollary 5.8; the main upper and lower bounds do not rely on it.

minor comments (3)
  1. [Lemma 4.6] The conditioning step 'Fix the identity of p... the occupied rank set remains a uniformly random k-subset' relies on the independence part of Lemma 3.1. The statement is correct, but one explanatory sentence explicitly invoking that independence would make the argument easier to parse.
  2. [Corollary 4.9] The numerical verification mixes precisions: Psi(0.31684) < 4.26738 while 3+4mu = 4.26736. Giving both values to the same number of digits would make the claimed margin easier to check.
  3. [Corollary 5.8] The strict separation statement depends on the external full-space uniform-cost bound of [HJ26]. The surrounding text states this, but Corollary 5.8 itself could carry a one-line reminder that this is an external input, so a reader skimming the result is not misled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper and lower bound proofs are self-contained; the only external input is the independent [HJ26] uniform-cost bound used solely for the model-separation corollary.

full rationale

I walked the paper's derivation chain in good faith. The 4.2674 upper bound (Theorem 4.8, Corollary 4.9) is an internal derivation: Algorithm 1 is defined independently, Lemmas 4.1–4.7 supply the analysis, and the parameter μ is chosen by solving Ψ(μ)=3+4μ near μ=0.31684. No quantity that is later called a prediction is fitted from data or from the target result; μ is chosen to balance two derived coefficients, not to force the constant. The 3−o(1) lower bound (Theorem 5.1, Corollary 5.7) is also self-contained: Lemmas 5.2–5.6 establish the fixed random-order instance from an i.i.d. construction, and the replacement argument in Corollary 5.7 is a direct online simulation. The only genuinely external load-bearing input is the cited [HJ26] sub-2.42 uniform-cost upper bound, used exclusively in Corollary 5.8 for the uniform/nonuniform separation; it is not by the present authors and is not used to prove the main upper or lower bound. Appendix A explicitly says it adapts Huang and Jiang's rank-cutoff framework but supplies its own proofs (Theorem A.2 and Theorem A.6) and its own class-optimality statement, and the paper openly scopes that statement to the Candidate Marginal TimeDist class. There is no self-citation chain, no uniqueness theorem imported from the authors' prior work, no ansatz smuggled in by citation without proof, and no renaming of a known result as organization. The known-horizon limitation is disclosed in Remark 2.1 and Section 6, and the paper does not claim the same guarantee when the horizon is unknown; this is scoping, not circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central results rest on a small number of domain assumptions: the random-order known-horizon model, the cited HJ26 uniform-cost upper bound, and standard metric/probability facts. The only tunable free parameter is μ, chosen by continuous optimization rather than data fitting. The lower-bound construction uses artificial facilities y_I, but these are instances, not new postulated physical or algorithmic entities.

free parameters (1)
  • μ = 0.31684 (balance point of Ψ(μ) and 3+4μ; appendix uses μ*≈0.140215)
    Algorithm parameter that sets λ_t=min{1,q_t/μ}. It is chosen to optimize the worst-case ratio, not fitted to instance data; still a free design parameter in the algorithm.
assumptions (5)
  • domain assumption Random-order model: adversary fixes a demand multiset U; arrival order is uniform; horizon n is known to the algorithm.
    Section 2 and Remark 2.1. The upper-bound algorithm uses q_t=t/n; the lower bounds hold even when the horizon is known.
  • domain assumption Huang-Jiang's <2.42 competitive ratio for full-space uniform costs is correct.
    Used in Corollary 5.8 for the strict separation; the paper does not re-derive this external result.
  • standard math Metric triangle inequality and standard hypergeometric tail identities.
    Used across Lemmas 4.3-4.7 and Lemma 3.1 for first-rank and later-rank probabilistic bounds.
  • domain assumption Optimal solution clusters have positive opening costs, so empty clusters can be removed without increasing cost.
    Section 4.2 relies on positive opening costs to assume every optimal cluster is nonempty.
  • standard math Conditional on the demand multiset, an i.i.d. demand sequence is a uniformly random ordering of its copies.
    Lemma 5.6 converts the i.i.d. lower-bound construction into a fixed-multiset random-order lower bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Random-Order Online Facility Location Beyond Uniform Opening Costs." pith.science (2026). https://pith.science/paper/T7YJUNAL

@misc{pith2026260722496,
  author       = {Pith},
  title        = {Pith review of: Random-Order Online Facility Location Beyond Uniform Opening Costs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T7YJUNAL}},
  note         = {Machine review of arXiv:2607.22496}
}
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)+\lambda_t f_y$, where $\lambda_t=\min\{1,q_t/\mu\}$, 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 1 linked inside Pith

  1. [1]

    Improved online algorithms for knapsack and GAP in the random order model

    Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, 83(6):1750--1785, 2021

    2021

  2. [2]

    Online facility location with multiple advice

    Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021

    2021

  3. [3]

    A simple and deterministic competitive algorithm for online facility location

    Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. A simple and deterministic competitive algorithm for online facility location. Information and Computation, 194(2):175--202, 2004

    2004

  4. [4]

    C. J. Argue, Alan Frieze, Anupam Gupta, and Christopher Seiler. Learning from a sample in online algorithms. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 13852--13863, 2022

    2022

  5. [5]

    Online graph algorithms with predictions

    Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35--66, 2022

    2022

  6. [6]

    Robust algorithms for the secretary problem

    Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. Robust algorithms for the secretary problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS), 2020

    2020

  7. [7]

    Better streaming algorithms for clustering problems

    Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better streaming algorithms for clustering problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 30--39, 2003

    2003

  8. [8]

    Online facility location with deletions

    Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online facility location with deletions. In 26th Annual European Symposium on Algorithms (ESA), pages 21:1--21:15, 2018

    2018

Show all 30 references
  1. [9]

    A primal--dual algorithm for online non-uniform facility location

    Dimitris Fotakis. A primal--dual algorithm for online non-uniform facility location. Journal of Discrete Algorithms, 5(1):141--148, 2007

    2007

  2. [10]

    On the competitive ratio for online facility location

    Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1--57, 2008

    2008

  3. [11]

    Online and incremental algorithms for facility location

    Dimitris Fotakis. Online and incremental algorithms for facility location. ACM SIGACT News, 42(1):97--131, 2011

    2011

  4. [12]

    Improved bounds for online facility location with predictions

    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, 39(25):26973--26981, 2025

    2025

  5. [13]

    Clustering data streams: Theory and practice

    Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):515--528, 2003

    2003

  6. [14]

    On the facility location problem in online and dynamic models

    Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. On the facility location problem in online and dynamic models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 176 of LIPIcs, pages 42:1--42:23, 2020

    2020

  7. [15]

    Random order online set cover is as easy as offline

    Anupam Gupta, Gregory Kehne, and Roie Levin. Random order online set cover is as easy as offline. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1253--1264, 2022

    2021

  8. [16]

    Random-order models

    Anupam Gupta and Sahil Singla. Random-order models. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 234--258. Cambridge University Press, 2021

    2021

  9. [17]

    Yichen Huang and Shaofeng H.-C. Jiang. The power of arrival times in random-order online facility location. arXiv:2607.10564, 2026

    2026 arXiv

  10. [18]

    Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang

    Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In International Conference on Learning Representations (ICLR), 2022

    2022

  11. [19]

    Competitive analysis with a sample and the secretary problem

    Haim Kaplan, David Naori, and Danny Raz. Competitive analysis with a sample and the secretary problem. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2082--2095, 2020

  12. [20]

    Online weighted matching with a sample

    Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1247--1272, 2022

    2022

  13. [21]

    Almost tight bounds for online facility location in the random-order model

    Haim Kaplan, David Naori, and Danny Raz. Almost tight bounds for online facility location in the random-order model. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1523--1544, 2023

    2023

  14. [22]

    o nnis, and Berthold V \

    Thomas Kesselheim, Klaus Radke, Andreas T \"o nnis, and Berthold V \"o cking. Primal beats dual on online packing LPs in the random-order model. SIAM Journal on Computing, 47(5):1939--1964, 2018

    1939

  15. [23]

    Secretary problems with non-uniform arrival order

    Thomas Kesselheim, Robert Kleinberg, and Rad Niazadeh. Secretary problems with non-uniform arrival order. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 879--888, 2015

    2015

  16. [24]

    Knapsack secretary with bursty adversary

    Thomas Kesselheim and Marco Molinaro. Knapsack secretary with bursty adversary. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 72:1--72:15, 2020

    2020

  17. [25]

    Online facility location against a t -bounded adversary

    Harry Lang. Online facility location against a t -bounded adversary. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1002--1014, 2018

    2018

  18. [26]

    On competitive ratio for online uniform facility location problem in random-order model

    Mengzhen Li, Runjie Miao, Chenchen Wu, and Dachuan Xu. On competitive ratio for online uniform facility location problem in random-order model. Theoretical Computer Science, 1072:115878, 2026

    2026

  19. [27]

    Online facility location

    Adam Meyerson. Online facility location. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 426--431, 2001

    2001

  20. [28]

    Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam

    Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1690--1701, 2012

    2012

  21. [29]

    Online and random-order load balancing simultaneously

    Marco Molinaro. Online and random-order load balancing simultaneously. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1638--1650, 2017

    2017

  22. [30]

    Williamson

    Chandrashekhar Nagarajan and David P. Williamson. Offline and online facility leasing. Discrete Optimization, 10(4):361--370, 2013

    2013

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.