{"id":"b9295e22-6f0d-457d-9e2b-2424343c96ad","arxiv_id":"2607.05342","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-factor approximations for exact-ratio fair k-center are obtained by combining fairlets with a controlled number of outliers from majority groups.","lead":"The paper gives constant-factor approximation algorithms for fair k-center clustering that enforce exact demographic ratios by discarding a minimal number of outliers. This lets practitioners obtain exactly balanced clusters even when the raw data ratios are awkward or coprime.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim is a clean, combinatorial extension of the fairlet framework of Chierichetti et al. to the setting where the input ratios do not already match the target. The proofs follow the classic pattern (cheap fairlets that agree with an optimum + 2-approx Gonzalez on anchors) and the paper carefully states the one-sided-outlier precondition under which the guarantees hold. The reader's weakest_assumption is therefore accurate as a modeling limitation, but it does not undermine the theorems as written. No deeper technical gap (incorrect triangle-inequality chaining, missing capacity argument, or experimental contradiction) surfaces on a second reading. The recommended concrete test simply reconfirms the most elementary diameter claim that underpins every subsequent bound; if it holds, the rest of the analysis is standard. Consequently the ACCEPT verdict with high confidence remains appropriate.","tokens_in":46626,"tokens_out":511,"duration_ms":5126,"concrete_test":"Independently re-derive the cost bound of Corollary B.3 (or the multi-color analogue C.2) from the existence of an agreeing fairlet decomposition of diameter 2 OPT (Lemma B.2) without using the flow network of Algorithm 3; if the 2 OPT fairlet radius fails to hold for some metric instance satisfying the cardinality preconditions, the 4-approximation collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags the one-sided-outlier restriction (Definition 1.3 and the regime of Section 1.2), but this is an explicit modeling choice of the paper rather than a hidden flaw in the proofs. Theorems 2.2, 2.3 and 3.1 are stated and proved only under the precondition that the minority class is fully covered and outliers are taken exclusively from the majority classes; the algorithms never claim guarantees when an optimum must discard minority points. The two-sided variant (Theorem 3.2) is treated separately and yields a weaker 11-approximation, again under an explicit lower bound on z. The combinatorial arguments (fairlet existence via Lemmas B.2/D.1, flow/matching constructions, and the φ+ρ cost bound of Lemma 2.1) are standard and appear complete. Experimental comparisons are limited but consistent with the theory. No internal inconsistency or unstated assumption that would invalidate the stated approximation claims was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies fair k-center clustering under exact demographic ratio constraints when the input point set does not already realize those ratios. It introduces a one-sided-outlier model that discards the minimal number of majority-class points so that the remaining set admits a t1:t2:...:tm-fairlet decomposition, then clusters the anchors of those fairlets. Algorithm 1 combined with the flow-based fairlet routines (Algorithms 3–5) yields a center-aware 4-approximation for the 1:t and 1:t2:...:tm cases (Theorems 2.2, 2.3) and a 14-approximation for arbitrary integer ratios (Theorem 3.1); a separate two-sided-outlier variant for the balanced two-color case gives an 11-approximation (Theorem 3.2). The analysis rests on standard triangle-inequality and max-flow arguments (Appendices A–D). Experiments on four UCI-style data sets compare the informed-outlier approach against random majority-class discarding and confirm lower clustering cost.","tokens_in":46863,"tokens_out":607,"duration_ms":5162,"significance":"The work supplies the first combinatorial constant-factor approximations that enforce exact target ratios on arbitrary inputs by a controlled use of outliers. Because the algorithms reduce to classical max-flow and Gonzalez farthest-first traversal, they are practical and come with publicly released code. The automatic ratio-rounding rule (t1=1, ti=floor(|Hi|/|H1|)) makes the method immediately applicable to real demographic data without manual parameter tuning. These contributions fill a clear gap between the exact-representation literature (which requires the input already to be balanced) and the LP-based approximate-representation literature (which sacrifices exactness).","major_comments":[],"minor_comments":[{"comment":"Section 3.1 and Figure 6: the 8-approximation lower-bound construction for the inlier-center variant is clear, yet a short remark that the same construction does not apply when anchors are restricted to the minority class would help readers appreciate why the design choice is essential.","section":null},{"comment":"Appendix D.1 (two-sided outliers): the non-center-aware 11-approximation is stated cleanly, but the subsequent center-aware 14-approximation is only sketched in Observation D.14; expanding the argument by a few lines would make the appendix self-contained.","section":null},{"comment":"Tables 3–8 (Appendix H): the raw input-to-ideal ratio lists are useful, yet a one-sentence summary of the typical number of discarded outliers per data set would make the experimental section easier to parse without consulting the appendix.","section":null},{"comment":"Figure 4: the caption claims a matching lower bound for the 4-approximation; adding the concrete distances used in the construction would let readers verify the tightness claim without reconstructing the figure.","section":null}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The useful move here is simple: keep exact fairlets (so the combinatorial structure stays intact) and let a minimal, one-sided outlier budget absorb the mismatch between the input cardinalities and the target integer ratio. That is new relative to Chierichetti et al. and the later exact-representation papers, which either force the input to already be balanced or switch to interval relaxations and LP rounding.\n\nWhat they deliver is clean. For the practically relevant 1:t and 1:t2:…:tm settings they get a center-aware 4-approximation by max-flow fairlets on the minority class as anchors plus Gonzalez on those anchors (Theorems 2.2 and 2.3). The general t1:…:tm case needs capacitated multi-center anchors and jumps to 14 (Theorem 3.1); the two-sided-outlier variant is an 11-approx (non-center-aware). All the proofs are standard triangle-inequality + flow/matching arguments and look complete. They also ship open-source code and run the natural comparison against random-outlier baselines on the usual UCI sets; the informed outliers win, as expected.\n\nSoft spots are real but proportional. The one-sided restriction (never discard minority points) is an explicit modeling choice, not a hidden flaw; if an optimum must throw away minority points the guarantees simply do not apply. The general-case algorithm is less practical because of the capacitated subroutine. Experiments are limited to four data sets and modest k, but they are consistent with the theory and not oversold. Citation pattern is appropriate; no circularity.\n\nThis is for people who already work on fairlets or constrained clustering and want a combinatorial tool that actually runs on unbalanced real data. It does not rewrite the field, but it fills a genuine modeling gap cleanly. I would send it to peer review without hesitation.","headline":"Clean combinatorial fix for exact-ratio fair k-center when the input ratios are ugly; solid 4-approx for the practical 1:t cases, code shipped.","tokens_in":47427,"tokens_out":491,"would_cite":true,"duration_ms":6310,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Fair k-center can match exact group ratios on messy data by discarding a few majority outliers, with constant-factor guarantees.","keywords":["fair clustering","k-center","outliers","fairlets","approximation algorithms","demographic fairness","ratio preservation"],"falsifier":"Construct a two-color instance whose unique low-cost 1:1 solution must discard at least one minority point; if every algorithm that never discards minority points returns a radius more than four times the true optimum, the claimed guarantee fails.","tokens_in":47586,"feed_emoji":"⚖️","tokens_out":549,"duration_ms":5477,"temperature":0.7,"pith_summary":"Real data rarely has group sizes that already match a target ratio such as 1:1 or 1:2:3. Earlier fair clustering either assumed perfect input ratios or relaxed fairness to approximate intervals. This paper shows how to keep the exact-ratio requirement while still handling arbitrary inputs: treat the excess points of majority groups as outliers whose number is fixed by the target ratio and the minority class size. The resulting problem stays combinatorial. Fairlets (minimal exact-ratio micro-clusters) are built by max-flow or capacitated-center subroutines; ordinary farthest-first traversal is then run only on the fairlet anchors. The pipeline yields a center-aware 4-approximation for every ratio of the form 1:t or 1:t2:...:tm and a 14-approximation for fully general integer ratios. Experiments on standard demographic data sets confirm that informed outlier selection produces lower clustering cost than random discarding.","feed_headline":"Exact fair ratios via majority outliers, 4-approx","feed_subtitle":"Combinatorial fairlets keep exact group proportions even when input sizes do not match.","key_machinery":"Fairlet decomposition with anchors restricted to the minority class (Algorithms 3-5 inside the framework of Algorithm 1). The fairlets realize the exact target ratio while covering the minority class completely; farthest-first traversal on the anchors then produces the final centers, and the triangle inequality bounds the total radius by the sum of fairlet cost and anchor clustering cost.","core_discovery":"By allowing a prescribed number of majority-class outliers, every target integer ratio becomes feasible, and the classic fairlet-plus-k-center pipeline continues to give constant-factor center-aware approximations: 4 for one-sided ratios that begin with 1, and 14 for arbitrary t1:...:tm.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Exact ratios via majority outliers in fair k-center (4-approx)","Outliers unlock exact group proportions for fair k-center","Fairlets plus outliers preserve exact ratios, constant-factor","Majority outliers enable exact t1:...:tm fair k-center","Exact ratio fair k-center by prescribed majority outliers"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"Outliers may never be taken from the minority color class; the number of outliers is completely determined by the target ratio and the size of that minority class.","fun_headline_variants_meta":{"raw":{"variants":["Exact ratios via majority outliers in fair k-center (4-approx)","Outliers unlock exact group proportions for fair k-center","Fairlets plus outliers preserve exact ratios, constant-factor","Majority outliers enable exact t1:...:tm fair k-center","Exact ratio fair k-center by prescribed majority outliers"]},"model":"grok-4.5","effort":"low","cost_usd":0.005898,"raw_usage":{"total_tokens":1531,"prompt_tokens":726,"num_sources_used":0,"completion_tokens":70,"cost_in_usd_ticks":58980000,"prompt_tokens_details":{"text_tokens":726,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":735,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":726,"tokens_out":70,"duration_ms":5542,"temperature":1.0,"reasoning_tokens":735,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T07:15:22.808086+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct a two-color instance whose unique low-cost 1:1 solution must discard at least one minority point; if every algorithm that never discards minority points returns a radius more than four times the true optimum, the claimed guarantee fails.","supporting_citations":[],"review_version":2}