{"id":"ed4d68f6-daf3-4f49-8542-5c8743f9acdc","arxiv_id":"2506.08673","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For two-color data, the paper provides the first constant-factor approximation algorithms for closest fair clustering and for fair consensus clustering under the generalized mean objective.","lead":"This paper introduces two new problems in fair machine learning: turning an unfair clustering into the closest fair one, and combining several clusterings into one fair consensus clustering. It gives an optimal algorithm when group sizes are equal and constant-factor approximations for unequal group sizes, with NP-hardness results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 1 in Appendix C.2.1 — the structural lemma that an optimal balanced clustering splits each input cluster with at most one part of size ≥ p and keeps all red points in that part — is the load-bearing unverified step for the 17- and 33-approximation theorems.","rationale":"Good-faith reading: the paper's core positive results are the constant-factor approximations for closest fair clustering, and the consensus reductions are straightforward and correct given those primitives. The reductions (Theorem 18 and Theorem 38) are clean, and I see no issue there. The 1:1 exact algorithm (Theorem 1) also has a plausible exchange argument, though the appendix is typo-heavy. The decisive point is the balancing step for p>1. The entire p:1 analysis reduces to Claim 1: the fixed-point structure of the optimal balanced clustering. The reader's weakest assumption identified the same claim, and I agree that this is the load-bearing concern. I do not claim Claim 1 is false; I claim the written proof does not settle it beyond reasonable doubt because it is long, uses a series of exchange arguments with subtle size-boundary conditions, and is not machine-checked. The concrete test I propose directly checks the claim on all small instances; because the approximation factors 17 and 33 are constants, even a counterexample at p=2 or p=3 with small n would overturn the theorems as stated. If the test finds no counterexample, the conditional verdict should stand and the paper should move toward acceptance after cleanup. If it finds one, the balancing lemma needs replacement or the approximation factors need revision. This is why I keep the verdict unchanged from the reader's CONDITIONAL. Separately, Section G is referenced but not present in the reviewed text; this is a completeness issue for the NP-hardness claim, not for Theorems 2 and 3.","tokens_in":73147,"tokens_out":16447,"duration_ms":204383,"concrete_test":"Run an exhaustive counterexample search for the structural Claim 1: for p ∈ {2,3,4} and n ≤ 12, enumerate all input clusterings D of red/blue points with global blue:red = p:1, compute a closest balanced clustering T* by brute force over all set partitions (or by a verified ILP), and test, for every input cluster D_i, whether the parts D_i ∩ T*_j satisfy either (i) one part contains all red(D_i) and all other parts have size < p, or (ii) all parts have size < p. If any instance violates the claim, Theorem 20 is false and the 17-approximation collapses; if none does, extend the same test to the fractional setting of Section D and to p=5 with randomized instances. A secondary analytical check is to re-derive Claim 7's ILP lower bound without invoking Claim 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The 17- and 33-close bounds (Theorems 2 and 3) are obtained by composing, via Theorem 18, a 3.5- or 7.5-close balancing algorithm (Theorems 20 and 21) with a 3-close fairing algorithm (Theorem 19). The balancing analysis in Section C is anchored by Claim 1 (Appendix C.2.1): in an optimal balanced clustering T*, every input cluster D_i that is split has either (i) one part X_{i,j}=T*_{r_j} containing all of red(D_i), with all other parts of size < p, or (ii) every part of size < p. Claim 7 uses exactly this to assert that T* cuts the same number W_g/p of surplus p-subsets as the algorithm, and Claim 10 uses it to equate the optimal ILP choice of cut subsets with the algorithm's greedy choice. If Claim 1 fails, the lower bound in Lemma 24 and the equivalence in Claim 10 can both fail, so the stated 3.5-approximation for p:1 is unsupported; Section D inherits the same defect for fractional p:q, and therefore Theorems 2 and 3 are not established. The proof of Claim 1 is a long chain (Claims 2-6) with boundary-sensitive inequalities, and the paper contains no machine-checked verification or released implementation. A small counterexample to Claim 1 — e.g., a red-rich cluster split into several large parts to absorb external blue surplus — would invalidate the 17-approximation as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper initiates the study of Closest Fair Clustering and Fair Consensus Clustering for red-blue colored points. For the perfectly balanced 1:1 case it claims an exact O(n log n) algorithm; for integral ratio p:1 and fractional p:q it claims 17-close and 33-close approximations, obtained by composing a balancing step with a making-fair step; for ℓ-mean fair consensus clustering it gives a generic (2+α)-approximation, yielding factors 3, 19, and 35 in the three ratio settings. The composition theorems (Theorem 18 and Theorem 38) are clean and appear correct if the constituent approximation lemmas hold. The decisive and least verified parts are the structural analysis of optimal balanced clusterings in Appendix C, the fractional balancing analysis in Appendix D, and the pseudocode for the balancing and fairing algorithms, where several load-bearing steps are incomplete or internally inconsistent.","tokens_in":73390,"tokens_out":12066,"duration_ms":158585,"significance":"If the technical lemmas are correct, the results would be valuable: constant-factor approximation guarantees for closest fair clustering that are independent of p and q, an exact polynomial algorithm for the 1:1 case, and the first approximation algorithm for fair consensus clustering under the generalized mean objective. The paper is refreshingly free of fitted parameters: the claimed constants are universal and derived from the proofs. The high-level two-stage architecture and the consensus reduction are believable. However, the main approximation theorems rest on long appendix arguments, especially the structural Claim 1 and the ILP-greedy equivalence in Appendix C.2, and the version I read contains algorithmic typos and a possibly invalid step in the proof of Claim 1. No machine-checked proofs or released implementation accompany the appendices, so the central guarantee is not yet independently verified.","major_comments":[{"comment":"The construction of M in the proof of Claim 5 is not a valid clustering as written: the formula M = T* \\ {T*_{r_k} | k∈[t]} ∪ {(X_{i,j} ∪ Y), (T*_{r_ℓ} \\ Y_ℓ | ℓ≠j)} removes all T*_{r_k} but does not place the sets Z_1,...,Z_t anywhere, although the subsequent distance computation uses |Z_ℓ| and treats Z_ℓ as merged with T*_{r_ℓ} \\ Y_ℓ. With this gap, the proof that X_{i,j} = T*_{r_j} is incomplete, and therefore Claim 1 is not established. Claim 1 is used in Claim 7 to assert that T* cuts the same W_g/p surplus p-subsets as the algorithm and in Claim 10 to equate the ILP optimum with the greedy choice; without a correct proof of Claim 1, Theorem 20 and, through Theorem 18, Theorems 2 and 3 are unsupported.","section":"Appendix C.2.1, Claim 5"},{"comment":"The ILP lower bound is not justified. The subsets W_{i,z} are introduced as 'numbered arbitrarily' (Appendix C.1), but the ILP imposes the prefix constraint x_{i,z} ≤ x_{i,z'} for z > z', and the proof asserts that if |∪_{ℓ≠j} X_{i,ℓ}| = ap + s_i then 'T* has cut W_{i,0},...,W_{i,a}'. Since the numbering is arbitrary, there is no structural reason for an optimal balanced clustering to cut a prefix of this numbering. Consequently the identification of the optimal cut choices with the algorithm's greedy minimum-cost choices in Claim 10 does not follow, and the bound dist(D,T) ≤ 3dist(D,T*) in the merge case (Lemma 22/27) is not proven.","section":"Appendix C.2.2, Claim 7 and Eqs. (25)-(27)"},{"comment":"The pseudocode for AlgoforGeneralPQ defines RMERGE as {D_i | s_r(D_i) ≤ q/2} and BMERGE as {D_i | s_b(D_i) ≤ q/2}, which is the opposite of the intended merge sets (and uses q/2 rather than p/2 in the blue case). As written, the algorithm would classify every cluster as a merge-type cluster, contradicting the case analysis in Section D.1 and making the claimed behavior of the fractional balancing algorithm incorrect. This is a load-bearing implementation error, not merely a typographical nuisance, because the four-case analysis in Section D.3 depends on these sets.","section":"Algorithm 7, lines 2 and 4"},{"comment":"Algorithm 12 does not output a partition of V for inputs that contain already-fair clusters. A cluster T_i with |blue(T_i)| = ρ|red(T_i)| is put in neither TYPERED nor TYPEBLUE, and F is initialized to empty and only updated inside the two later loops. Hence already-fair clusters are omitted from the returned clustering. Since Theorem 19 is stated for an arbitrary balanced clustering and relies on Algorithm 12, the making-fair step is not correctly implemented by the pseudocode as written.","section":"Appendix E.1, Algorithm 12"},{"comment":"The comparison between the fractional and integral balancing costs is not demonstrated. Eq. (85) defines cost2(D_i)^blue = (p - s_r(D_i))(|D_i| - s_r(D_i)), using the red surplus s_r in what should be a blue merge cost, while the p:1 comparison cost in Eq. (86) uses the blue surplus s(D_i). This makes the claimed inequality cost2(Q)^blue ≤ cost2(T) dimensionally inconsistent as written. The subsequent 3OPT bound for the blue costs in the cut-merge case (Claim 22) is therefore not established.","section":"Section D.3.2, Eq. (85) and Claim 22"}],"minor_comments":[{"comment":"The update 'Set 1 = Set 2 \\ CRed' should read 'Set 1 = Set 1 \\ CRed'; the current line would remove from the wrong set.","section":"Algorithm 3, line 15"},{"comment":"The displayed distance comparison contains undefined indices and refers to C(2) before that object is introduced, which makes verification of Theorem 1 materially harder than it should be.","section":"Appendix A, proof of Lemma 13"},{"comment":"The lemma numbering is inconsistent: the merge-case statement is numbered Lemma 22 in one place and Lemma 27 in another, Lemma 24 is repeatedly called Theorem 24, and similar patterns appear in Section D.3. The text should be carefully renumbered before resubmission.","section":"Throughout Appendices C and D"},{"comment":"In the blue-surplus loop, the iteration is written as 'for C_i ∈ CUT'' while the parameter of the subroutine is BCUT; this is presumably a typo but should be corrected.","section":"Algorithm 8, line 15"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are potentially interesting and the reduction skeleton is sound, but the paper is not ready for publication in its current form: the structural proof behind Claim 1 has a concrete gap, the ILP equivalence in Claim 7/10 is not justified, and two of the central pseudocodes (Algorithm 7 and Algorithm 12) contain errors that change the behavior of the algorithms. I would ask for a full rewrite of Appendices C-E with the structural claims stated as separate verified lemmas, and preferably with small-scale empirical or machine-checked verification of the key combinatorial inequalities. I did not see Section G (NP-hardness) in the material provided, so I cannot assess that part of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing: the paper defines two new problems—closest fair clustering and fair consensus clustering—and gives the first constant-factor approximations for them; and the clean reduction in Theorem 18 (balanced + fair → close fair) is the genuinely solid piece. The 1:1 exact algorithm is also elegant, and the claims are consistently stated in terms of the right objective.\n\nThe work is honestly new: the problem formulations don't appear in the fair correlation clustering literature, and the approximation factors are independent of p and q, which is a real improvement over the O(p^2) fair-correlation-clustering route. The reduction from consensus clustering to closest fair clustering (Theorem 38) is simple, correct, and worth keeping.\n\nThe soft spots are in the appendices. The 17- and 33-close theorems rest on Claim 1 (Appendix C.2.1), the structural lemma about how an optimal balanced clustering splits an input cluster. The stress-test flags this as load-bearing and unverified. I read the exchange arguments in Claims 2–6; they are plausible and I don't see an obvious counterexample, so I don't think the whole paper collapses. But the presentation is dense, with enough typos and notational slips (e.g., Algorithm 7's set definitions, the mixing of κ and µ formulas) that I would not take the constants 17 and 33 as established until a careful rewrite and independent verification. The NP-hardness proof for unequal ratios is only referenced, not present in this manuscript, which is a gap for the claimed completeness. No machine-checked proofs or code are shipped, so the review burden is real.\n\nProportionately: this is a solid, well-motivated contribution to the fair-clustering subfield, not a field re-organizer. The central argument likely holds, but it needs referee-level cleanup. I'd send it to peer review without hesitation, with the expectation of a major revision on the appendices. I wouldn't cite it yet in my own work for the specific constants; the problem definitions are citable now.\n\nRecommendation: engage with it—assign a serious referee who can check the boundary cases in Section C.","headline":"New problem definitions with clean reductions and a likely-correct but messy proof core; worth a serious referee.","tokens_in":73984,"tokens_out":2639,"would_cite":false,"duration_ms":30945,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that the closest fair clustering of any input clustering can be computed exactly in O(n log n) when groups are equal, and within constant factors 17 and 33 in near-linear time when the blue-to-red ratio is integral…","keywords":["fair clustering","consensus clustering","closest fair clustering","approximation algorithms","balanced clustering","disparate impact","NP-hardness","correlation clustering"],"falsifier":"Compute an exact closest balanced clustering by exhaustive search or integer programming on small red-blue instances with $p\\in\\{2,3,4\\}$ and random input clusterings, and inspect every optimal solution: if any original cluster is split into two pieces both of size at least $p$, or has red points in more than one piece, Claim 1 is false and the proof's lower bounds fail.","tokens_in":72886,"feed_emoji":"⚖️","tokens_out":8977,"duration_ms":101511,"temperature":0.7,"pith_summary":"This paper studies consensus clustering under the fair-clustering constraint that every output cluster contains blue and red points in the population ratio p:q. Its central object is the closest fair clustering of an arbitrary input clustering: the fair clustering that disagrees with the input on the fewest point pairs. The paper claims this problem is exactly solvable in $O(n\\log n)$ when the population is perfectly balanced, and admits 17-close (integral ratio $p:1$) and 33-close (fractional $p:q$) approximations in near-linear time, with approximation factors independent of $p$ and $q$. If correct, practitioners can postprocess any clustering to enforce proportionate representation while provably bounding the amount of disruption, and the same repair subroutine yields constant-factor approximations for fair consensus clustering under the whole $\\ell$-mean family of objectives.","feed_headline":"Closest fair clustering: exact at 1:1, 17-close beyond","feed_subtitle":"Even with uneven groups, the nearest fair clustering is only a constant factor away in disagreements.","key_machinery":"The argument is carried by a two-stage repair pipeline. The first stage, balancing, moves surplus points of one color between clusters so that each cluster's blue count is a multiple of $p$ and red count a multiple of $q$, through cut-merge decisions based on per-cluster surplus and deficit; this stage is claimed to be 3.5-approximate for integral ratios and 7.5-approximate for fractional ratios. The second stage, making fair, redistributes surplus red points from clusters that are too red to clusters that are too blue, and is claimed 3-approximate. Composing a 3.5- or 7.5-close balanced clustering with a 3-close fair clustering gives $17 = 3.5 + 3 + 3.5\\cdot 3$ and $33 = 7.5 + 3 + 7.5\\cdot 3$. For the 1:1 case the mechanism differs: a maximal fair cluster is cut from each input cluster and a greedy merge over the leftover monochromatic pieces is shown optimal.","core_discovery":"On the paper's own terms, the discovery is that fairness repair is tractable despite the NP-hardness of fair variants of most clustering objectives. For equal red and blue counts, an optimal nearest fair clustering exists and can be found in $O(n\\log n)$; for any unequal ratio $p:q$, no optimal repair can be found in polynomial time unless P = NP, but a fair clustering within a constant factor of the optimal disagreement distance can always be computed in $O(n\\log n)$. The ratio independence of the 17 and 33 constants is the substantive point: the approximation cost does not grow with the skew of the protected groups.","pith_inferences":["If the structural property behind the balancing analysis holds in full generality, the same surplus/deficit accounting may extend to more than two protected colors by replacing the ratio with a vector of proportions, though the constants would likely degrade with the number of groups.","A direct empirical test would compare the output of the 17- and 33-close algorithms with exact optimal repairs on small instances; the paper's analysis upper-bounds the gap, and the true gap may be far smaller.","The exact 1:1 greedy merge suggests a general principle: in disagreement metrics, retaining the largest fair sub-cluster of each input cluster is never wasteful, and an analogous rule may be useful in related constrained-partition problems such as balanced correlation clustering."],"forward_implications":["Any input clustering can be postprocessed to satisfy proportionate representation with a provable 17- or 33-close guarantee in pairwise disagreement, independent of how skewed the blue-to-red population ratio is.","Fair consensus clustering inherits constant-factor approximations for the median, center, and every $\\ell$-mean objective between them, with factors 3, 19, and 35.","The 1:1 case separates closest fair clustering from fair correlation clustering: the latter is NP-hard even when the ratio is one, while the former is exactly solvable in $O(n\\log n)$.","Any improvement to the balancing step automatically improves the closest-fair factor through $(\\alpha+\\beta+\\alpha\\beta)$ and the fair-consensus factor through $2+\\alpha$.","Because the problem is NP-hard at unequal ratios, exact polynomial repair is impossible unless P = NP, so constant-factor approximation is the right target."],"supporting_citations":[{"why":"Defines fair clustering via proportionate blue-to-red representation, the constraint this paper enforces.","marker":"Chierichetti et al. (2017)"},{"why":"Supplies the pairwise-disagreement distance and the 11/7-approximation for median consensus that the fair consensus results build on.","marker":"Ailon et al. (2008)"},{"why":"Shows consensus clustering is APX-hard, motivating constant-factor approximation for the fair version.","marker":"Bonizzoni et al. (2008)"},{"why":"Provides fair correlation clustering approximation algorithms, the baseline that the ratio-independent 17-close guarantee improves on.","marker":"Ahmadian et al. (2020)"},{"why":"Shows fair correlation clustering is NP-hard even at ratio one, the comparison point for the exact 1:1 result.","marker":"Ahmadi et al. (2020)"},{"why":"Gives the better-than-2 approximation for center consensus clustering, an objective covered by the $\\ell$-mean fair consensus framework.","marker":"Das and Kumar (2025)"}],"fun_headline_variants":["Closest fair clustering: optimal at 1:1, constant-factor otherwise","Fair consensus clustering: exact for balanced, constant-approx for p:q","First fair consensus clustering: constant-factor for any ratio","Nearest fair clustering: optimal for 1:1, constant-factor for unequal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"In the optimal balanced clustering of any input, each original cluster is split so that at most one piece is as large as $p$ and all of that cluster's red points stay inside that large piece; if this structural property fails, the 3.5-approximation for balancing, and hence the 17- and 33-close results, collapse.","fun_headline_variants_meta":{"raw":{"variants":["Closest fair clustering: optimal at 1:1, constant-factor otherwise","Fair consensus clustering: exact for balanced, constant-approx for p:q","First fair consensus clustering: constant-factor for any ratio","Nearest fair clustering: optimal for 1:1, constant-factor for unequal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001568,"raw_usage":{"total_tokens":6242,"prompt_tokens":909,"completion_tokens":5333,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":5254}},"tokens_in":525,"tokens_out":5333,"duration_ms":41473,"temperature":1.0,"reasoning_tokens":5254,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:05:09.211422+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute an exact closest balanced clustering by exhaustive search or integer programming on small red-blue instances with $p\\in\\{2,3,4\\}$ and random input clusterings, and inspect every optimal solution: if any original cluster is split into two pieces both of size at least $p$, or has red points in more than one piece, Claim 1 is false and the proof's lower bounds fail.","supporting_citations":[],"review_version":1}