Pith. sign in

REVIEW 5 major objections 4 minor 22 references

Towards Fair Representation: Clustering and Consensus

T0 review · 5 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict New problem definitions with clean reductions and a likely-correct but messy proof core; worth a serious referee. read the letter →

arxiv 2506.08673 v3 pith:HYMNKDXE submitted 2025-06-10 cs.LG cs.DS

Diptarka Chakraborty , Kushagra Chatterjee , Debarati Das , Tien Long Nguyen , Romina Nobahari This is my paper · ORCID
classification cs.LGcs.DS MSC 68W2568Q1762H30
keywords fairclusteringconsensusclosestapproximationalgorithmsbalanceddisparateimpactNP-hardnesscorrelation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

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.

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 (5)
  1. [Appendix C.2.1, Claim 5] 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.
  2. [Appendix C.2.2, Claim 7 and Eqs. (25)-(27)] 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.
  3. [Algorithm 7, lines 2 and 4] 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.
  4. [Appendix E.1, Algorithm 12] 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.
  5. [Section D.3.2, Eq. (85) and Claim 22] 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.
minor comments (4)
  1. [Algorithm 3, line 15] The update 'Set 1 = Set 2 \ CRed' should read 'Set 1 = Set 1 \ CRed'; the current line would remove from the wrong set.
  2. [Appendix A, proof of Lemma 13] 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.
  3. [Throughout Appendices C and D] 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.
  4. [Algorithm 8, line 15] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the constant-factor approximation claims are derived from self-contained structural lemmas, and the consensus-clustering reduction is a legitimate theorem composition.

full rationale

The paper's central results (Theorems 2 and 3) are obtained by composing a balancing approximation (Theorems 20 and 21) with a fairing approximation (Theorem 19) via Theorem 18, which is a standard triangle-inequality composition. The balancing analyses in Sections C and D rest on structural claims about the optimal balanced clustering (e.g., Claim 1 in Appendix C.2.1) that are proved from first principles through exchange arguments and lower-bound inequalities (Claims 2–6, Lemma 24, Proposition 26); these do not assume the target approximation ratio or any fitted parameter. The 17- and 33-close bounds are universal constants derived by adding per-cluster lower bounds on OPT and upper bounds on algorithm costs, not by calibrating to data or by renaming an input quantity. The fair consensus clustering algorithm (Theorem 38) reduces consensus to closest fair clustering, which is a legitimate algorithmic reduction: the closest-fair theorems are independently proved, and the reduction only uses the approximation guarantee as a black box with triangle inequality. Self-citations in the paper, such as the reference to Chakraborty et al. (2022) in the introduction, appear only as related-work context and are not load-bearing for any theorem. The reader's flagged concern about Claim 1 is a potential correctness gap in a long proof, not a circularity: the claim is an unverified structural lemma, but it is not equivalent by definition to the output bound, and the paper does not import it from a self-citation. Since no prediction is fitted and no load-bearing step reduces to its own input by construction, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper contains no fitted parameters or ad hoc constants: the approximation factors (17, 33, 3.5, 7.5, 3, 19, 35) are universal and derived in the proofs. The only background inputs are standard metric and number-theoretic facts and the problem's own fairness constraint.

assumptions (4)
  • standard math The pairwise-disagreement distance between clusterings satisfies the triangle inequality.
    Invoked in Theorem 18 to compose balancing and making-fair approximations, and in Theorem 38 for consensus clustering.
  • domain assumption The input guarantees the total blue-to-red ratio is exactly p/q with p,q coprime, so a fair clustering exists.
    Definition 8 and used in Sections C and E to match total surplus with total deficit.
  • domain assumption For coprime p and q, a cluster whose blue-to-red ratio is p/q has blue count divisible by p and red count divisible by q.
    Used to justify that every fair clustering is balanced, which is the starting point of the two-stage framework in Section B.
  • standard math Standard inequalities such as Chebyshev's sum inequality are valid for the cost lower bounds.
    Used in the cut-case and merge-case analyses of the balancing algorithms in Appendix C.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Fair Representation: Clustering and Consensus." pith.science (2026). https://pith.science/paper/HYMNKDXE

@misc{pith2026250608673,
  author       = {Pith},
  title        = {Pith review of: Towards Fair Representation: Clustering and Consensus},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HYMNKDXE}},
  note         = {Machine review of arXiv:2506.08673}
}
read the original abstract

Consensus clustering, a fundamental task in machine learning and data analysis, aims to aggregate multiple input clusterings of a dataset, potentially based on different non-sensitive attributes, into a single clustering that best represents the collective structure of the data. In this work, we study this fundamental problem through the lens of fair clustering, as introduced by Chierichetti et al. [NeurIPS'17], which incorporates the disparate impact doctrine to ensure proportional representation of each protected group in the dataset within every cluster. Our objective is to find a consensus clustering that is not only representative but also fair with respect to specific protected attributes. To the best of our knowledge, we are the first to address this problem and provide a constant-factor approximation. As part of our investigation, we examine how to minimally modify an existing clustering to enforce fairness -- an essential postprocessing step in many clustering applications that require fair representation. We develop an optimal algorithm for datasets with equal group representation and near-linear time constant factor approximation algorithms for more general scenarios with different proportions of two group sizes. We complement our approximation result by showing that the problem is NP-hard for two unequal-sized groups. Given the fundamental nature of this problem, we believe our results on Closest Fair Clustering could have broader implications for other clustering problems, particularly those for which no prior approximation guarantees exist for their fair variants.

Figures

Figures reproduced from arXiv: 2506.08673 by the authors.

Figure 1
Figure 1. Visualization of the algorithm to find a closest fair clustering for equi-proportionally bal￾anced input. In each cluster, xB (resp., yR) denotes that the number of blue (resp., red) points is x (resp., y). In Step 2, we introduce a greedy strategy to combine R1, R2, . . . , Rϕ into a set of fair clusters. We begin by selecting the smallest cluster Ri . Without loss of generality, assume Ri consists of blue points. … view at source ↗
Figure 2
Figure 2. Visualization of the scenario when only merge clusters remain after executing AlgoGen￾eral, which converts (a) to (b). Now, the total deficit W = 5, and thus, depending on the cutcost − mergecost, either an already cut cluster needs to be cut further (depicted in (b)), or a single merge cluster needs to be cut (depicted in (c)). In each cluster, xB (resp., yR) denotes that the number of blue (resp., red) points is x… view at source ↗
Figure 3
Figure 3. Visualization of the scenario when only cut clusters remain after executing AlgoGeneral. The extra surplus points of clusters D3, D4, D5 form an extra cluster E1 of size p, con￾taining only blue points. In each cluster, xB (resp., yR) denotes that the number of blue (resp., red) points is x (resp., y). even more clusters and create a cluster of size 2p instead of p. However, through careful analysis, we show that ac… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    if s(D i)≤p/2thenOPT Di ≥s(D i)(|Di| −s(Di)) +1 2 s(Di)(p−s(D i))

    work page

  2. [2]

    35 CHAKRABORTYCHATTERJEEDASNGUYENNOBAHARI For proving Theorem 24, we need the help of the following proposition

    if s(D i)> p/2thenOPT Di ≥(p−s(D i))(|Di| −s(Di)) +1 2 s(Di)(p−s(D i)). 35 CHAKRABORTYCHATTERJEEDASNGUYENNOBAHARI For proving Theorem 24, we need the help of the following proposition. Proposition 25Consider any integerp≥2, andα 1, . . . , αt ∈[p], fort≥1. Lets= Pt i=1 αi modp. Then Pt i=1 αi (p−α i)≥s(p−s). Proof:Suppose,(α 1 +α 2) modp=s 1, hence(α 1 +α...

    work page

  3. [3]

    Ifb≤p/2, thenA≥b(n−b)

    work page

  4. [4]

    Proof:Without loss of generality, assume thatx 1 ≤x 2 ≤ · · · ≤xt

    Ifb > p/2, thenA≥(p−b)(n−b). Proof:Without loss of generality, assume thatx 1 ≤x 2 ≤ · · · ≤xt. (1) Suppose thatb≤p/2. We show thatA≥b(n−b). Asx t = max{xi}, it follows thatA≥ P i<j xixj = Pt i=1 xi n−x i 2 ≥n n−x t 2 . Additionally,A≥x t(n−x t)+(x t −bt)qt. LetB=n n−x t 2 , andC=x t(n−x t)+(x t −bt)qt. ThenA≥BandA≥C. Therefore, it suffices so thatB≥b(n−b...

    work page

  5. [5]

    Either∃j∈[t], such thatX i,j =T ∗ rj (for someT ∗ rj ∈ T∗)and red(D i)⊆X i,j and|X i,ℓ|< p ∀ℓ̸=j

    work page

  6. [6]

    Now, to prove the previous claim, we need to prove the other claims below

    or|X i,ℓ|< p,∀ℓ∈[t]. Now, to prove the previous claim, we need to prove the other claims below. Claim 2Consider a partitionX i,j ofD i. Suppose,X i,j ⊆T ∗ rj (for someT ∗ rj ∈ T∗) then|T ∗ rj \ Xi,j| ≤si,j wheres i,j =|blue(X i,j)|modp. Proof:Suppose for a partitionX i,j,|T ∗ rj \X i,j|> s i,j. To prove this first we constructMfrom T ∗ such thatdist(D,M)<...

    work page

  7. [7]

    , Yj−1, Yj+1,

    DivideYinto(t−1)disjoint partsY 1, Y2, . . . , Yj−1, Yj+1, . . . , Yt such that •|Y ℓ|=|blue(X i,ℓ)| ∀ℓ̸=jand • S ℓ̸=j Yℓ =Y

    work page

  8. [8]

    RemovetclustersT ∗ rℓ for allℓ∈[t]fromT ∗

    work page

Show all 22 references
  1. [9]

    We move the red points ofX i,ℓ for allℓ̸=jto the setT ∗ rj

    Addtnew clusters toM • First cluster :D i ∪(T ∗ rj \(X i,j ∪Y)) • Remaining(t−1)clusters :(T ∗ rℓ \X i,ℓ)∪Y ℓ)∀ℓ̸=j. We move the red points ofX i,ℓ for allℓ̸=jto the setT ∗ rj. The main part of the above construction is that we have dividedYinto(t−1)disjoint parts Y1, Y2, . . ...

  2. [10]

    Either∃j∈[t], such thatX i,j =T ∗ rj (for someT ∗ rj ∈ T∗)andred(D i)⊆X i,j and|X i,ℓ|< p ∀ℓ̸=j

  3. [11]

    This implies [ ℓ̸=j Xi,ℓ modp=s i Hence, [ ℓ̸=j Xi,ℓ =ap+s i for some constanta

    or|X i,ℓ|< p∀ℓ∈[t]. This implies [ ℓ̸=j Xi,ℓ modp=s i Hence, [ ℓ̸=j Xi,ℓ =ap+s i for some constanta. Let us partition the setblue(Di)into subsetsW i,0, Wi,1, . . . , Wi,m such thatm= (|blue(D i)| −si)/p where|W i,0|=s i and|W i,z|=pfor allz >0. If S ℓ̸=j Xi,ℓ =ap+s i then we s...

  4. [12]

    CuttingW i,0 fromD i is :κ 0(Di) =si(|Di| −si) 49 CHAKRABORTYCHATTERJEEDASNGUYENNOBAHARI

  5. [13]

    Recall inT ∗,D i gets split intoX i,1,

    CuttingW i,z fromD i forz >0is :κ z(Di) =p(|Di| −(zp+si)). Recall inT ∗,D i gets split intoX i,1, . . . , Xi,t. We say a clusterD i ∈ Dalso belongs to a setCUT-OPT (say) ift >1; otherwise, it belongs to a setMERGE-OPT (say). Informally,T ∗ has cut some points from the clusters...

  6. [14]

    For eachD i ∈MERGE,s i ≥ p

    Hences i(p−s i)≥s i p 2 ≥s 2 i . For eachD i ∈MERGE,s i ≥ p

  7. [15]

    These observations imply that X Di∈CUT\CUT ′ 1 2 s2 i + X Di∈MERGE 1 2 d2 i + X Di∈CUT ′ si(p−s i) 2 ≤ X Di∈D si(p−s i) 2 ≤OPT, where the last inequality is from Claim 12

    Hences i(p−s i)≥ p 2 (p−s i)≥d 2 i (whered i = (p−s i)). These observations imply that X Di∈CUT\CUT ′ 1 2 s2 i + X Di∈MERGE 1 2 d2 i + X Di∈CUT ′ si(p−s i) 2 ≤ X Di∈D si(p−s i) 2 ≤OPT, where the last inequality is from Claim 12. This completes the proof. 58 TOWARDSFAIRREPRESEN...

  8. [16]

    Now we are ready to prove Theorem 23

    Combining these facts, we get A≤A ′ +|E| 1 2 3 p2 16 + p2 16 =A ′ +|E| p2 8 ≤ 3 2 A′, which is desired. Now we are ready to prove Theorem 23. 62 TOWARDSFAIRREPRESENTATION: CLUSTERING ANDCONSENSUS Proof of Theorem 23:LetTbe the output of AlgoforGeneral() in the cut case. Letcos...

  9. [17]

    Cost paid by AlgoforGeneralPQ() in Cut-Merge caseThe algorithm AlgoforCut-Merge()(Algorithm 9) pays the following set of disjoint costs • From each clusterD i ∈REDCUT, AlgoforGeneralPQ() cuts the red surplus parts r(Di)from Di. Hence, the cost paid for cutting these red surplu...

  10. [18]

    Cost paid by optimal clusteringQ ∗ in cut-merge case Claim 21cost 1(Q)Red +cost 2(Q)Red +cost 3(Q)Red +cost 4(Q)Red ≤3.5dist(D,Q ∗). Proof:Recall inp: 1case, whereTis the output of AlgoforGeneral()(Algorithm 4) we have cost1(T) = X Di∈CUT si(|Di| −si) (Refer toEq.(42)) =cost 1...

  11. [19]

    Let us assumeW i,z,r denotes thezth red subset of the clusterD i.y i,z,r takes the value1if we cutzth red subset fromD i

    Cost paid byAlgoforMerge-Merge(Algorithm 11)The algorithmAlgoforMerge-Merge(Algorithm 11) pays the following set of disjoint costs 84 TOWARDSFAIRREPRESENTATION: CLUSTERING ANDCONSENSUS • From the red side, we cut multiple subsets of sizeq. Let us assumeW i,z,r denotes thezth r...

  12. [20]

    Claim 25cost 1(Q)blue +cost 1(Q)blue +cost 3(Q)blue +cost 4(Q)blue ≤3dist(D,Q ∗)

    Cost paid by optimal clusteringQ ∗ in merge-merge case Claim 24cost 1(Q)red +cost 1(Q)red +cost 3(Q)red +cost 4(Q)red ≤3dist(D,Q ∗). Claim 25cost 1(Q)blue +cost 1(Q)blue +cost 3(Q)blue +cost 4(Q)blue ≤3dist(D,Q ∗). The proof of the previous two claims is the same as the proof ...

    1975

  13. [21]

    More specifically, consider any two integersp, q≥2such thatp/q >1 + √

  14. [22]

    Then the closest fair clustering problem on red-blue colored points where the ratio between the total number of blue and red points isp/q, is NP-hard. We can show this result by making the following modifications to the reduction: Take monochromatic red clustersR i’s of sizeqx...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.