{"id":"cc2a9254-f120-413d-a125-88203e0430eb","arxiv_id":"2607.10564","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Arrival-time information yields a deterministic 2.42-competitive algorithm and a 2.59-competitive randomized algorithm for random-order online facility location that retains the optimal adversarial-order ratio.","lead":"The paper breaks the long-standing 3-competitive barrier for random-order online facility location by letting opening decisions depend on arrival time as well as distance. It supplies a deterministic algorithm below 2.42 and a randomized algorithm below 2.59 that still matches the optimal adversarial-order guarantee.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly flags the relaxed-process domination as the most delicate analytic step, yet that step is only used to upper-bound HC; even if the domination is not tight the claimed competitive ratios remain valid upper bounds, and the paper already supplies a matching lower bound of ≈2.519 for the same family. The DistCut analysis is elementary and is shown optimal inside TimeDist. Both algorithms are fully specified, the free parameters are optimized against the paper’s own expressions, and the adversarial-order robustness argument is a routine adaptation of the classical DistProb analysis. Consequently the reader’s ACCEPT / HIGH-confidence verdict stands; no adjustment is warranted.","tokens_in":26721,"tokens_out":447,"duration_ms":5174,"concrete_test":"Independently recompute the continuum maximizer of F_α(L)=1-e^{-αL}+(1-α)L e^{-αL} and solve  (1-α)/α exp(-1/(1-α))=2α; confirm that α*≈0.293 yields max{1+ρ,2(1+α)}≈2.586 and that the discrete two-phase sequence of Corollary 4.2 stays within O(1/n) of this value.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on self-contained analyses of two simple algorithmic families (μ-DistCut and qt-DistProb). For DistCut the first-arrival anchor argument (Lemmas 3.2–3.4) is elementary and is matched by a matching TimeDist lower bound (Theorem 5.3). For qt-DistProb the geometry-free domination (Definition 4.10 / Lemma 4.11) and equalization (Lemma 4.13) are the only non-standard steps; both are proved by induction and averaging that appear correct on inspection, and the resulting 2.59 figure is already known to be slightly loose relative to the family lower bound of ≈2.519 (Theorem 5.2). No hidden assumption that would invalidate either competitive-ratio claim is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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).","tokens_in":26968,"tokens_out":685,"duration_ms":7016,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"A few minor typos appear (e.g., “DistCutadmits” missing space, occasional missing punctuation after display equations). A light copy-edit pass would clean them.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and well within the scope of a top algorithms journal. The only analytic step that is slightly non-standard (the geometry-free domination of H_C) is carefully proved and already known to leave a small gap to the family lower bound; I see no reason to request further tightening before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: using arrival time as a density signal lets them beat the long-standing 3-competitive barrier for random-order online facility location. They get a deterministic cutoff algorithm under 2.42 and a time-varying DistProb variant under 2.59 that still keeps the optimal adversarial-order guarantee. That is a real advance on Meyerson and on Kaplan–Naori–Raz.\n\nWhat is new is the TimeDist idea itself. Prior request-local rules only looked at distance; the paper proves that any time-oblivious rule is stuck at 3, so the improvement is forced by the new information. The deterministic μ-DistCut is especially clean: open if distance exceeds min{1, z_t/μ}. The analysis anchors only at the first request of each offline cluster, uses a simple tradeoff between cluster size and first-arrival time, and is matched by a TimeDist lower bound of the same constant. The qt-DistProb analysis is heavier (balanced openings via center excess, then a geometry-free relaxed process plus equalization), but the steps are written out and the resulting 2.59 sits only a little above their own family lower bound of ~2.519. The free parameters are optimized against their own analytic expressions, not fitted to data.\n\nSoft spots are minor and already acknowledged. DistCut is fragile in adversarial order (they give an Ω(√n) lower bound). The 2.59 figure is slightly loose relative to the family lower bound, which is expected once you dominate by an adversarial excess process. The global lower bound remains 2, so the gap is not closed. None of this undercuts the claims that are proved.\n\nThis is for people who work on online metric algorithms or random-order models. The proofs are self-contained and the algorithms are simple enough to implement offline in O(n²). I would send it to peer review without hesitation; the math looks solid and the contribution is concrete. Worth reading and citing if you touch this area.","headline":"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.","tokens_in":27565,"tokens_out":511,"would_cite":true,"duration_ms":6249,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W40","90C27"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["online facility location","random-order model","competitive analysis","arrival time","DistProb","TimeDist","metric facility location"],"falsifier":"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.","tokens_in":27648,"feed_emoji":"⏱️","tokens_out":754,"duration_ms":7871,"temperature":0.7,"pith_summary":"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.","feed_headline":"Arrival times cut online facility location below 2.42","feed_subtitle":"A deterministic clock-aware rule beats the long-standing 3 barrier while a second rule stays good against adversaries","key_machinery":"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).","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Arrival times cut deterministic facility location under 2.42","Time-aware thresholds beat 3 barrier in random-order facility location","Arrival-time rule yields 2.42-competitive online facility location","Facility location drops to 2.42 using arrival times for openings","Clock-dependent openings improve facility location to 2.42 and 2.59"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Arrival times cut deterministic facility location under 2.42","Time-aware thresholds beat 3 barrier in random-order facility location","Arrival-time rule yields 2.42-competitive online facility location","Facility location drops to 2.42 using arrival times for openings","Clock-dependent openings improve facility location to 2.42 and 2.59"]},"model":"grok-4.5","effort":"low","cost_usd":0.00663,"raw_usage":{"total_tokens":1657,"prompt_tokens":732,"num_sources_used":0,"completion_tokens":78,"cost_in_usd_ticks":66300000,"prompt_tokens_details":{"text_tokens":732,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":847,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":732,"tokens_out":78,"duration_ms":9137,"temperature":1.0,"reasoning_tokens":847,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T10:46:50.962116+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}