{"id":"02b490dd-b895-4dd3-89f5-56b8413a6f5d","arxiv_id":"2506.13191","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The proposed (2+ε) and (7+ε) FPT algorithms for colorful sum of radii are not proven: the sampling argument misses small clusters and the residual-instance lemma uses one center too few.","lead":"The paper claims the first constant-factor FPT approximation algorithms for the colorful sum of radii problem, a fair-clustering variant with per-group outlier limits. Both main proofs contain serious gaps, so the central claims are not established as written.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6/Corollary 7 use k−i centers to cover k−i+1 remaining optimal clusters, so the residual radius bound and Theorem 4's (7+ε) guarantee fail.","rationale":"The reader's weakest assumption matches the most serious defect I find: Section 4.1's residual-instance analysis miscounts clusters. At iteration i, after covering i−1 clusters, there are k−i+1 uncovered optimal clusters, but the residual instance is assigned only k−i centers. Because Lemma 6 and Corollary 7 underpin Lemma 8, which bounds every Col-Cen radius by 2β˜r_i, the cost bound sum r̂_j ≤ (2β+1) sum ˜r_j in Lemma 10 depends on a false premise. The defect is not merely a missing constant: the i = 1 case already shows the residual k-center radius can be Θ(diameter) while 2r*_1 is small, whenever clusters are separated and outlier budgets are tight. This is an internal inconsistency, not a disagreement with consensus. I also note the Theorem 2 probability argument has the singleton-sampling problem the reader flags, but the Theorem 4 flaw alone is decisive because it breaks the algorithm's core inductive step. The concrete test above (two separated one-dimensional clusters with m = 0) settles the matter: the claimed bound fails immediately at the first invocation of Col-Cen. Hence the central claims are not established; the reader's REJECT verdict stands unchanged. In fairness, the framework idea of iteratively using a colorful k-center oracle is plausible, but the residual-instance lemma would need a correct center count or a different covering invariant to support it.","tokens_in":10981,"tokens_out":5207,"duration_ms":60035,"concrete_test":"Take the line metric with two colors, P1 = {0, 1}, P2 = {100, 101}, k = 2, m = (0, 0). The optimal sum-of-radii solution uses centers 0.5 and 100.5 with radii 0.5 each, so r*_1 = 0.5. Run Algorithm 3 at iteration i = 1: B is empty, so P′ = P and the subroutine Col-Cen is invoked with k−i = 1 center and m′ = 0. Any single center covering all four required points has radius at least 50, while 2r*_1 = 1. Thus Corollary 7 (and hence Lemma 8) is violated: the returned radius is not bounded by 2β˜r_1 for any reasonable β. This directly invalidates the approximation-ratio proof of Theorem 4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 6 and Corollary 7 (Section 4.1) contain a center-count mismatch. At the start of iteration i, exactly i−1 optimal clusters have been covered, so the residual point set P′ still contains the points of k−i+1 optimal clusters (C*_i, ..., C*_k). Lemma 6 nevertheless asserts an upper bound on the optimal largest radius of the residual instance I′ = (P′, d, k−i, m′) with only k−i centers. In general, k−i centers cannot serve k−i+1 clusters, and the per-class outlier bounds m′ may rule out discarding one cluster. The proof's claim that all remaining points can be covered by one ball of radius at most 2r*_i is not justified: well-separated clusters are not mutually within O(r*_i). Consequently, Lemma 8's bound ¯r_i ≤ 2β˜r_i and the (2β+1+ε) cost analysis of Theorem 3 break already at iteration i = 1. Since Theorem 4 is the application of Theorem 3, its (7+ε) guarantee is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the colorful sum of radii problem, in which points are partitioned into color classes and each class has a per-class outlier bound. The goal is to choose k centers and assign points to clusters while leaving at most m_i points from class P_i unassigned, minimizing the sum of cluster radii. The paper claims the first constant-factor FPT approximation algorithms for this problem: a (2+ε)-approximation running in time O(n^2 log^k(k/ε)(k+m)^{k+m}) via an iterative random-covering scheme, and a (7+ε)-approximation running in time O(nω^2((k+m)log(k/ε))^k) by iteratively invoking a colorful k-center subroutine.","tokens_in":11176,"tokens_out":5093,"duration_ms":58211,"significance":"If correct, the results would be a meaningful contribution: the colorful sum of radii generalizes outlier-robust sum of radii, and constant-factor FPT algorithms with separate parameter dependence on k and on m are natural targets. The paper uses external subroutines (e.g., the Jia et al. colorful k-center algorithm) and does not fit free parameters to data, so the circularity concern is low. However, both main theorems contain load-bearing gaps in their probability and center-count analyses, and the errors are structural rather than cosmetic. The significance of the claimed contribution is therefore not established by the current manuscript.","major_comments":[{"comment":"The success probability analysis omits the probability of sampling a point from each optimal cluster. In each of the k+m selections in Lines 9-10, the proof conditions on having selected the correct radius but does not account for the fact that the uniformly chosen point must belong to the appropriate optimal cluster. A singleton optimal cluster is hit with probability only 1/|P| in a uniform draw, and the probability of hitting all k optimal clusters and the m outlier positions can be as small as (k+m)!/n^{k+m} or worse. Repeating the procedure (k+m)^{k+m} times per profile therefore does not give a constant success probability, and the claimed (2+ε)-approximation guarantee of Theorem 2 is unsupported.","section":"Section 3, Theorem 2 proof and Algorithm 1"},{"comment":"The center-count mismatch is load-bearing. At the start of iteration i, the algorithm has already covered clusters C*_1,...,C*_{i-1}, so the residual point set P' still contains points from k-i+1 optimal clusters C*_i,...,C*_k. Lemma 6 asserts that the residual instance I'=(P',d,k-i,m') has optimal largest radius at most 2r*_i, but in general k-i centers cannot cover k-i+1 well-separated clusters, and the per-class outlier bounds m' do not allow discarding an entire cluster. The proof's statement that all remaining points can be covered by one ball of radius at most 2r*_i is false when the remaining optimal clusters are far apart. Consequently Corollary 7 and Lemma 8 fail, and the (2β+1+ε) cost analysis of Theorem 3, and hence Theorem 4, is not supported.","section":"Section 4.1, Lemma 6 and Corollary 7"},{"comment":"The Counting algorithm contains an implementation error. In Line 4, inside the loop over covered points, it sets ρ'_i ← ρ_i + 1, which adds the original requirement ρ_i for every covered point instead of incrementing by one. Then, in Line 8, the loop overwrites the result with max{0, ρ_i}, so the function returns the unupdated requirement rather than the number of points still required to be covered. This makes the computation of the residual outlier vector m' in Algorithm 3 incorrect, independently of the center-count issue in Lemma 6.","section":"Section 4.1, Algorithm 2"}],"minor_comments":[{"comment":"The derandomization remark is incomplete: it states that the entire random process can be derandomized by enumerating all possible radii, but Line 9 of Algorithm 1 also chooses points uniformly from a shrinking set P, and the remark does not explain how those choices are enumerated or bounded.","section":"Section 3, Remark 1"},{"comment":"The proof of Lemma 6 refers to Figure 4.1, but no figure appears in the manuscript text; the caption alone is insufficient to verify the claimed covering argument.","section":"Section 4.1, Lemma 6"},{"comment":"The notation for complexity bounds is inconsistent, e.g., O(log^k_{1+ε}(k/ε)) appears in Lemma 1 while the abstract and Theorem 2 use O(log^k(k/ε)); the base of the logarithm should be stated clearly everywhere.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The two main theorems have load-bearing gaps that appear unfixable by local edits: the probability bound in Theorem 2 ignores cluster-size effects, and the center-count mismatch in Lemma 6 invalidates the reduction in Section 4. The Counting pseudocode error adds a further correctness issue. These are not mere presentation problems, so I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Both main theorems fail as written. The problem is real—colorful sum of radii with per-class outlier bounds is a natural variant—and the idea of bootstrapping a sum-of-radii approximation from a colorful k-center subroutine is worth exploring. But the proofs have load-bearing errors that a careful reader will hit immediately.\n\nTheorem 2's analysis assumes that picking a random point and then a random radius from a profile has success probability at least 1/(k+m) per iteration. That would be true if the point were uniform over k clusters and m outliers, but it is uniform over all n points. A singleton cluster is sampled with probability 1/n, not 1/(k+m), so the claimed (k+m)^{k+m} repetitions do not yield constant success probability. The algorithm might be repairable with a different sampling scheme, but that is not what is proved.\n\nTheorem 4 rests on Lemma 6, which has a center-count mismatch. At iteration i, after covering i−1 of the k optimal clusters, the residual instance still contains points from k−i+1 clusters, yet the lemma bounds the optimal largest radius for an instance with only k−i centers. For well-separated clusters with tight outlier budgets, k−i centers cannot cover all remaining clusters, so the bound is false. Corollary 7 and Lemma 8 inherit the problem, and the (2β+1+ε) guarantee collapses. Algorithm 3 also uses σ_i(c*_i), which presumes knowledge of the optimal centers; without an explicit guessing scheme, the pseudocode is not executable.\n\nOn the positive side, the paper gives a clear formal setup and a sensible literature review. The running time of the second algorithm, exponential in k but not in m, is a worthwhile target. But the current proofs do not establish any of the advertised results. I would reject. If the authors can fix the sampling analysis and the residual-instance counting, the paper could become a real contribution, but that requires substantial work.\n\nFor your reading group: skip it unless you want an exercise in catching subtle parameter errors. I would not send this to a serious referee in its current state; it needs major revision and re-proofing first.","headline":"Both main theorems have load-bearing proof gaps, so the claimed FPT constant-factor approximations for colorful sum of radii are not established; the problem and high-level approach are promising but need major repair.","tokens_in":11722,"tokens_out":4766,"would_cite":false,"duration_ms":52819,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q25","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes the first constant-factor approximation algorithms for the colorful sum of radii problem that run in fixed-parameter tractable time: a (2+ε)-approximation and a (7+ε)-approximation.","keywords":["Colorful Sum of Radii","Outlier-Robust Clustering","Constant Approximation","Fixed-Parameter Tractable","Colorful k-center","Sum of Radii","Fair Clustering","Approximation Algorithms"],"falsifier":"In a metric with k well-separated singleton clusters and zero default outlier allowance, set n much larger than k and run Algorithm 1's random sampling; the actual probability that k uniform samples hit all k clusters is k!(k/n)^k, far below 1/k^k, so an instance large enough makes the (k+m)^{k+m} repetition bound insufficient for constant success probability. For Algorithm 3, take k-1 well-separated clusters plus a final cluster whose center lies inside an already chosen ball, with outlier budgets tight; compute the optimal radius of the residual (k-i)-center instance and check whether it exceeds 2r_i* — the lemma's claim fails when it does.","tokens_in":10758,"feed_emoji":"🎯","tokens_out":7340,"duration_ms":71488,"temperature":0.7,"pith_summary":"The paper targets the colorful sum of radii problem: partition a point set into color classes, choose k centers, and assign each non-outlier point to a center while allowing at most m_i outliers from class i, minimizing the sum of cluster radii. The authors claim the first constant-factor approximation algorithms for this problem that run in fixed-parameter tractable (FPT) time, with the exponential cost placed on the parameters k and m rather than on n. Concretely, they give a (2+ε)-approximation whose running time is exponential in both k and m, and a (7+ε)-approximation whose running time is exponential only in k, obtained by plugging a 3-approximation for colorful k-center into a general framework. The (2+ε) algorithm also applies directly to the classical outlier-robust sum of radii problem. This matters because it converts a problem with only a logarithmic approximation guarantee into one solvable to within a small constant, while keeping polynomial dependence on the data size.","feed_headline":"First constant-factor FPT algorithms for colorful sum of radii","feed_subtitle":"A (2+ε) algorithm and a (7+ε) algorithm handle outlier-robust clustering in FPT time.","key_machinery":"The load-bearing objects are the near-optimal radius profile and the iterative covering loop. Lemma 1 computes a small candidate set of radius vectors (r̃1,...,r̃k) with r_i* ≤ r̃_i ≤ (1+ε)r_i* by geometric discretization of the interval between a β-approximate k-center value and the optimal cost. In the (2+ε) algorithm, the profile is padded with m zero radii so outliers are treated as zero-radius balls; random point selection plus a guessed radius produces a ball of radius 2r̃_j that contains the entire optimal cluster, and the probability bound (k+m)^{-(k+m)} per profile drives the repetition count. In the (7+ε) algorithm, Lemmas 5-6 and Corollary 7 link colorful k-center to colorful sum of radii by bounding the optimal residual k-center radius by 2r_i*, so a β-approximate subroutine returns radius at most 2βr̃_i; the event E that the assignment σ_i routes the i-th optimal center to the right ball occurs with probability at least (k+m)^{-k}, and the enlarged radius (2β+1)r̃_i covers the cluster while the cost telescopes to (2β+1)(1+ε)OPT.","core_discovery":"The central claim is that the colorful sum of radii admits constant-factor approximations in FPT time. The first algorithm guesses a near-optimal radius profile by discretizing the interval from the optimal k-center radius to the optimal sum-of-radii cost, pads the profile with m zero radii for outliers, and repeatedly samples a point, draws an unused radius, and covers the point's optimal cluster with a ball of twice that radius; repeating the random process (k+m)^{k+m} times per profile yields constant success probability and total cost at most (2+ε)OPT. The second algorithm is a generic reduction: whenever a β-approximation for colorful k-center is available, iteratively peel off the largest remaining optimal cluster by running the k-center routine on the residual instance and covering the cluster with a ball of radius (2β+1) times the guessed radius, giving a (2β+1+ε)-approximation; with β=3 the result is 7+ε and the time bound is O($nω^{2}$((k+m)log(k/ε))^k). The paper presents these as the first constant-factor FPT approximations for the problem.","pith_inferences":["If the sampling analysis were tightened, the (2+ε) algorithm could likely avoid the (k+m)^{k+m} repetition factor, since the real bottleneck is hitting small clusters; a deterministic greedy cover might replace the random draws entirely.","Improving the colorful k-center approximation below 3 would immediately lower the 7+ε ratio, since the framework's guarantee is 2β+1.","The same covering-plus-residual framework should transfer to other sum-type objectives such as sum of diameters, wherever a k-center subroutine with per-color outlier control exists.","The two algorithms indicate a tradeoff curve: exponential dependence on m buys a better ratio (2+ε), while k-only dependence costs a larger constant (7+ε); closing this gap is a natural next step."],"forward_implications":["For any instance with k centers and m total outliers, a (2+ε)-approximation is computable in time O(n^2 log^k(k/ε)(k+m)^{k+m}).","Any future β-approximation for colorful k-center automatically yields a (2β+1+ε)-approximation for colorful sum of radii via Theorem 3.","With the current best 3-approximation for colorful k-center, the colorful sum of radii is (7+ε)-approximable in O(nω^2((k+m)log(k/ε))^k) time.","The outlier-robust sum of radii problem (the ω=1 case) inherits the (2+ε) FPT approximation.","The problem moves from a logarithmic approximation ratio to a small constant while remaining fixed-parameter tractable in k and m."],"supporting_citations":[{"why":"introduces the colorful sum of radii problem and gives the O(log ω)-approximation that this paper improves to a constant.","marker":"[9]"},{"why":"supplies the 3-approximation for colorful k-center used as the subroutine in Theorem 4.","marker":"[21]"},{"why":"introduces colorful clustering and provides the 2-pseudo-approximation for colorful k-center on which later k-center results build.","marker":"[3]"},{"why":"gives the FPT 2-approximation for sum of radii via radius-profile guessing, the method extended to the colorful setting.","marker":"[10]"},{"why":"provides the (3+ε)-approximation for outlier-robust sum of radii that the (2+ε) algorithm here matches and improves in FPT time.","marker":"[5]"},{"why":"used for the near-optimal radius-profile discretization approach that Lemma 1 adapts.","marker":"[6]"}],"fun_headline_variants":["First constant-factor FPT for colorful sum of radii","O(1)-approximation in FPT for colorful sum of radii","2+ε and 7+ε approximations for colorful radii in FPT","Colorful sum of radii now has constant-factor FPT algorithms","Constant-factor FPT for colorful radii"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the assumption that randomly sampling points will hit every optimal cluster within the allowed (k+m) draws with probability at least (k+m)^{-(k+m)}, and that after peeling off the largest clusters, the remaining points can be k-centered with radius at most twice the next optimal sum-of-radii radius.","fun_headline_variants_meta":{"raw":{"variants":["First constant-factor FPT for colorful sum of radii","O(1)-approximation in FPT for colorful sum of radii","2+ε and 7+ε approximations for colorful radii in FPT","Colorful sum of radii now has constant-factor FPT algorithms","Constant-factor FPT for colorful radii"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001937,"raw_usage":{"total_tokens":7635,"prompt_tokens":1059,"completion_tokens":6576,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":6492}},"tokens_in":675,"tokens_out":6576,"duration_ms":50070,"temperature":1.0,"reasoning_tokens":6492,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:41:49.362778+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"In a metric with k well-separated singleton clusters and zero default outlier allowance, set n much larger than k and run Algorithm 1's random sampling; the actual probability that k uniform samples hit all k clusters is k!(k/n)^k, far below 1/k^k, so an instance large enough makes the (k+m)^{k+m} repetition bound insufficient for constant success probability. For Algorithm 3, take k-1 well-separated clusters plus a final cluster whose center lies inside an already chosen ball, with outlier budgets tight; compute the optimal radius of the residual (k-i)-center instance and check whether it exceeds 2r_i* — the lemma's claim fails when it does.","supporting_citations":[{"cited_title":"Algorithms for covering multiple submodular constraints and applications","cited_arxiv_id":null,"evidence_quote":"introduces the colorful sum of radii problem and gives the O(log ω)-approximation that this paper improves to a constant."},{"cited_title":"Fair colorful k-center clustering","cited_arxiv_id":null,"evidence_quote":"supplies the 3-approximation for colorful k-center used as the subroutine in Theorem 4."},{"cited_title":"A constant approximation for colorful k-center","cited_arxiv_id":null,"evidence_quote":"introduces colorful clustering and provides the 2-pseudo-approximation for colorful k-center on which later k-center results build."},{"cited_title":"Parameter- ized approximation algorithms for sum of radii clustering and variants","cited_arxiv_id":null,"evidence_quote":"gives the FPT 2-approximation for sum of radii via radius-profile guessing, the method extended to the colorful setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the (3+ε)-approximation for outlier-robust sum of radii that the (2+ε) algorithm here matches and improves in FPT time."},{"cited_title":"Fpt approximations for fair k-min-sum-radii","cited_arxiv_id":null,"evidence_quote":"used for the near-optimal radius-profile discretization approach that Lemma 1 adapts."}],"review_version":1}