{"id":"6502a1cd-2a5a-46b3-bd01-9f211ba37d40","arxiv_id":"2607.22496","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"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.","lead":"A new algorithm for online facility location serves randomly arriving demand points with at most 4.2674 times the optimal cost even when opening costs differ between sites, improving the previous factor of 33. A companion lower bound shows no randomized algorithm can beat 3, and that uniform-cost and nonuniform-cost settings are genuinely different.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the 4.2674 upper-bound proof and the 3-o(1) lower bound are internally coherent; only the HJ26-based separation is externally dependent.","rationale":"The reader's weakest assumption was the known-horizon requirement plus the dependence on the cited HJ26 uniform-cost bound. I agree the HJ26 dependency is the main external risk: Corollary 5.8's strict separation CR_full_unif < 2.42 < 3 <= CR_full_nonunif is directly conditioned on the correctness of that preprint. However, this does not undermine the paper's central algorithmic claim (Theorem 4.8 / Corollary 4.9) or its self-contained lower bound (Theorem 5.1), both of which I could not find a flaw in after detailed checking of the charge arguments, rank-tail estimates, and the lower-bound transfer. The known-horizon assumption is part of the stated model and is explicitly disclosed, so I do not treat it as a weakness requiring a verdict change. The paper's main contribution is a substantial improvement over the previous factor 33 and a clean lower bound of 3; the separation is a corollary that inherits the usual citation risk but is clearly labeled. Therefore the reader's ACCEPT verdict remains appropriate.","tokens_in":24650,"tokens_out":28541,"duration_ms":280834,"concrete_test":"Independently verify the [HJ26] bound relied on by Corollary 5.8: re-derive or implement their full-space uniform-cost DistCut rule and confirm the competitive ratio is strictly below 2.42 on the sparse/dense instances used in their proof. If the constant is not below 2.42, reclassify the separation result as conditional, while keeping the main 4.2674 and 3-o(1) conclusions unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the full proof chain for Theorem 4.8 and Section 5 in good faith. Lemma 4.3 correctly bounds later-cluster costs via the monotone one-round charge and the upper-envelope decomposition; Lemma 4.5's rank-tail certificate and Lemma 4.6's high-cost excess are consistent; the cluster bookkeeping in Section 4.2 is exact. The lower bound's coverage-credit inequality (Lemma 5.4), the i.i.d.-to-random-order conditioning (Lemma 5.6), and the full-space replacement argument (Corollary 5.7) are all sound as stated. I found no internal inconsistency or hidden assumption beyond those explicitly declared. The one genuinely external load-bearing input is the cited [HJ26] sub-2.42 bound, used only in Corollary 5.8 for the uniform/nonuniform separation. If that contemporaneous preprint's bound were invalid or required different information assumptions, the separation would fail, but the paper's main upper-bound and lower-bound results would stand. The known-horizon assumption is explicit, correctly scoped, and is not a flaw in the stated model; the authors also clearly disclaim the unknown-horizon case.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24931,"tokens_out":17496,"duration_ms":185648,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Lemma 4.6"},{"comment":"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.","section":"Corollary 4.9"},{"comment":"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.","section":"Corollary 5.8"}],"recommendation":"accept","confidential_remarks":"I recommend acceptance. The central claims are sound and the presentation is careful. The only load-bearing external citation is [HJ26] in the final separation corollary, and the authors are transparent about its role. The AI-disclosure note is also transparent and does not affect the technical assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Strong paper. The headline is the deterministic 4.2674-competitive algorithm for random-order online facility location with arbitrary positive opening costs, improving Meyerson's 33. The lower bound is just as important: 3-o(1) for arbitrary randomized algorithms, already in the prescribed-site uniform-cost model, and transferred to full-space nonuniform costs. Combined with Huang-Jiang's sub-2.42, that gives a genuine separation between uniform and nonuniform full-space models. I checked the proof chain and it holds up. The upper bound uses a rank-dependent Lagrangian choice, a monotone one-round charge, and an upper-envelope decomposition; the cluster bookkeeping is exact. Lemma 4.5's rank tail is carefully handled, and the lower bound's coverage-credit inequality and i.i.d.-to-random-order conditioning are sound. No hidden fitting: the single parameter mu is chosen analytically at the intersection of the two coefficients.\n\nSoft spots are modest. The known-horizon assumption is real: q_t = t/n requires n, and the authors explicitly disclaim the unknown-horizon case, so this is a scope statement rather than a flaw. The separation corollary leans on the cited HJ26 sub-2.42 uniform-cost bound; if that preprint fails, the separation fails but the main results stand. The sharper 3.2805 unit-cost bound in Appendix A is a specialization and correctly labeled supplementary. No code or data, but that's normal for this genre and the proofs are self-contained enough.\n\nWho this is for: anyone working on random-order algorithms, facility location, or beyond-worst-case analysis. It closes a 12-fold gap and establishes the right model separation. The appendix's TimeDist lower bound is also a clean benchmark. I would send it to a serious referee without hesitation. My own verdict: accept, with the constants and the HJ26 dependency checked carefully.","headline":"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.","tokens_in":25392,"tokens_out":1272,"would_cite":true,"duration_ms":15022,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90B80","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["online facility location","random-order model","competitive ratio","nonuniform opening costs","rank-based algorithm","metric facility location","lower bound","prescribed candidate sites"],"falsifier":"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.","tokens_in":24551,"feed_emoji":"📍","tokens_out":7352,"duration_ms":75374,"temperature":0.7,"pith_summary":"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.","feed_headline":"4.2674 beats 33 for online facility location with uneven costs","feed_subtitle":"A deterministic rank-aware rule handles arbitrary opening costs and replaces the previous 33-factor guarantee with a ratio below 4.2674.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Facility location with uneven costs: ratio improved from 33 to 4.2674","Deterministic 4.2674-competitive algorithm for random-order facility location","Nonuniform opening costs tamed: 4.2674 beats old 33","Random-order facility location: 4.2674 competitive with arbitrary costs","Rank-aware rule yields 4.2674 guarantee for uneven facility costs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Facility location with uneven costs: ratio improved from 33 to 4.2674","Deterministic 4.2674-competitive algorithm for random-order facility location","Nonuniform opening costs tamed: 4.2674 beats old 33","Random-order facility location: 4.2674 competitive with arbitrary costs","Rank-aware rule yields 4.2674 guarantee for uneven facility costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000256,"raw_usage":{"total_tokens":1469,"prompt_tokens":856,"completion_tokens":613,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":509}},"tokens_in":600,"tokens_out":613,"duration_ms":6533,"temperature":1.0,"reasoning_tokens":509,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T04:33:14.875195+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}