Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering
Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen
cs.LG · cs.AI
Quick verdict
Claims 2.73–4.42 ratios for Euclidean fair k-center (FPT+streaming); sound core, but the 1+√2 improved proofs are deferred and Lemma 3's bound is wrong.
Summary
The paper studies fair k-center clustering in Euclidean spaces, where n points in m groups must be covered by k centers with at most k_l per group, minimizing the maximum assignment distance. Building on λ-independent center sets — maximal λ-separated subsets of size at most 2k for λ=√3r*, via an equilateral-triangle packing argument — the authors first give a fixed-parameter tractable (FPT) offline algorithm with ratio 1+√3≈2.732 (enumeration over candidates), improving the general-metric factor 3. Used as post-processing in a one-pass streaming framework, this yields 1+2√3+ϵ≈4.464, claimed improvable to 1+√2≈2.414 and 1+2√2+ϵ≈3.828, with proofs deferred to a 'full version'. A polynomial-time one-pass streaming algorithm (max-flow-based fairness repair over a 2r*-independent set) achieves 3+√3+ϵ≈4.732, tunable to ≈4.42 with O(hk log α) memory (h=122), marginally beating the 4.464 prior state of the art. Experiments on synthetic instances with known optima and three UCI datasets report lower clustering cost than baselines. Limitations: the improved-ratio proofs are incomplete, one appendix combinatorial bound appears mathematically wrong, the closest Euclidean streaming baseline is absent from the experiments, and the cost normalization in the real-data table is undefined.
Review complete
Assessment at a glance
6
risk flags identified
● high 1
● medium 3
● low 2
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A λ-independent center set with λ=√3r* has size at most 2k in Euclidean space, enabling the first FPT (1+√3)-approximation for Euclidean fair k-center, improving the general-metric factor 3 (Theorems 1-2).
- Embedding the FPT algorithm as post-processing in a one-pass streaming framework achieves 1+2√3+ϵ≈4.464, claimed improvable to 1+√2≈2.414 and 1+2√2+ϵ≈3.828 (proofs deferred).
- A polynomial-time one-pass streaming algorithm combining a 2r*-independent set with max-flow fairness repair achieves 3+√3+ϵ≈4.732, improvable to ≈4.42 with O(hk log α) memory (h=122), marginally beating the prior 4.464 SOTA.
- On synthetic instances with known optima and three UCI datasets, the proposed algorithms attain lower clustering cost than all compared baselines (Table 1, Figures 2-3).
Strengths
First FPT approximation for Euclidean fair k-center, beating the factor-3 barrier
Theorems 1-2 give a clean greedy-mapping-plus-enumeration construction with ratio 1+√3≈2.732 vs. the offline factor 3 of Jones et al. (2020); the λ=√3r* packing argument behind Lemma 1 (at most 2 points of an optimal ball pairwise farther than √3r*) is correct and reusable.
Tunable memory/ratio trade-off via geometric packing
Lemmas 10-11 generalize packing to λ=√(2+2/h)r* with |Γ|≤hk, yielding streaming ratio 3+√(2+2/h)≈4.42 at h=122 — a marginal but real improvement over 4.464, with the O(hk log α) memory cost stated honestly.
Polynomial-time streaming variant uses a well-chosen tool
Engineering completeness for a theory paper
Weaknesses
Headline improved ratios are unproven in this version
Lemma 3's enumeration bound is mathematically false as stated
Lemma 7's equivalence is half-proven; the infeasible branch is undefined
Closest streaming baseline missing from experiments
Experimental reporting gaps
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets fair k-center clustering in Euclidean spaces under the data-summarization model (Kleindessner et al., 2019): n points in m disjoint groups, k centers with at most k_l per group, minimizing maximum assignment distance. It advertises five guarantees: (i) an FPT offline algorithm with ratio 1+√3≈2.732 (Thm. 2); (ii) a one-pass streaming FPT variant at 1+2√3+ϵ≈4.464 (Lem. 4); (iii) improvements to 1+√2≈2.414 and 1+2√2+ϵ≈3.828; (iv) a polynomial-time one-pass streaming algorithm at 3+√3+ϵ≈4.732 (Thm. 3, Alg. 1); (v) a memory-tunable 3+√(2+2/h)≈4.42 at h=122 (Appendix D). Context matters: the offline factor-3 SOTA is Jones et al. 2020; the streaming SOTA it beats (4.464, Guo et al. 2026a) shares three co-authors with this paper.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 6 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What approximation ratio does this paper achieve for fair k-center clustering?
For Euclidean fair k-center it gives a fixed-parameter (FPT) offline algorithm with ratio 1+√3≈2.732 (claimed improvable to 1+√2≈2.414), a one-pass streaming FPT variant at 1+2√3+ϵ≈4.464 (claimed 3.828), and a polynomial-time one-pass streaming algorithm at 3+√3+ϵ≈4.732, tunable to about 4.42 with more memory — slightly better than the previous best of 4.464.
Is the code and data available for this paper?
Yes. The paper links a GitHub repository (ChaoqiJia/FPT_EuclideanFairk-Center) and uses public UCI datasets (Wholesale, Student, Adult) plus a synthetic-data construction with known optimum due to Kleindessner et al. (2019); experiments are CPU-scale Python.
What is the fair k-center problem?
Data points are split into m disjoint groups; one must pick at most k_l centers from group l (with total k) so every point is close to some chosen center, minimizing the maximum point-to-center distance. It is a data-summarization notion of fairness capping how many centers each group contributes.
Are the improved ratios 2.414, 3.828 and 4.42 fully proven in the paper?
Only partially. The 2.732, 4.464 and 4.732 guarantees are proven in the main text, while the improvements to 2.414 and 3.828 are stated with proofs deferred to a 'full version', and the 4.42 tuning relies on appendix lemmas without a complete ratio analysis; one appendix bound used for the runtime also contains an apparent error.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- PDF extraction garbles some mathematical notation (packing inequalities in Lemmas 1/11, several runtime expressions); the Lemma 3 counterexample was verified with independently computed values (C(40,10)) and does not depend on the garbled portions.
- The provided text ends after Appendix E.1's dataset footnotes; any appendix content beyond that point (e.g., further experimental subsections) is absent from the extraction.
- Figures 2, 3 and 5 are known only through captions and the authors' descriptions; plotted values could not be verified from text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.