Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read This paper proves that fair sum-of-radii clustering, for two color groups with balance parameter t and for balanced multi-color instances, admits the first polynomial-time constant-factor approximation algorithms.

desk verdict First poly-time constant-factor algorithm for fair sum-of-radii; the theorem looks right, and the stress-test's parity bug is a misreading—the real gap is an unproved vertex-disjointness claim that turns out to be harmless. read the letter →

arxiv 2504.14683 v2 pith:CMPAQQEX submitted 2025-04-20 cs.DS

Sina Bagheri Nezhad , Sayan Bandyapadhyay , Tianzhi Chen This is my paper · ORCID
classification cs.DS MSC 68W25
keywords fairclusteringsum-of-radiiapproximationalgorithmpolynomial-time(tk)-fairnessbalanceddegree-constrainedsubgraphclustermerging
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 establishes that fair clustering with the sum-of-radii objective—where each cluster must keep a red-to-blue ratio within [1/t, t] and the cost is the sum of cluster radii—admits the first polynomial-time constant-factor approximation. The two-group result gives a (144+ε)-approximation, and the balanced version with ℓ≥2 colors gives a (180+ε)-approximation, both in polynomial time. Previous constant-factor algorithms for this objective required time exponential in the number of clusters k, so the result moves fair sum-of-radii from fixed-parameter tractable territory into the same class as k-center. The proof works by reducing the fair problem to unconstrained sum-of-radii clustering on representatives of a carefully chosen star decomposition and showing, through a cluster-merging analysis, that this reduction loses only a constant factor.

What carries the argument

The load-bearing object is the minimum-cost degree-constrained spanning subgraph H of the complete bipartite graph between red and blue points, with each vertex degree in [1,t]; such a subgraph is necessarily a disjoint union of stars, and it can be computed in polynomial time via min-cost degree-constrained subgraph machinery. Around H the proof builds an auxiliary directed graph G* whose vertices are the optimal clusters and whose edges, marked 0 or 1 according to whether they run red-to-blue or blue-to-red, come from edges of H crossing cluster boundaries. The analysis follows minimum-switch paths—paths in G* with the fewest parity changes—and bounds their weighted length by repeatedly invoking the optimality of H: along each path the proof exhibits a removed edge set E'_1 containing the path and an added edge set E'_2 of small total weight that together restore a valid degree-constrained subgraph, so the path's weight cannot exceed the weight of E'_2. Hanging cycles and a sequence of cases (Lemmas 6–9) ensure the replacement edges exist and that each optimal cluster hosts few of them, yielding the bounds $w(E'_2)\le 6\sum_i r(C^*_i)$ in general and $\le 4\sum_i r(C^*_i)$ for switch-free paths.

What would settle it

Enumerate all small two-color instances, e.g., up to six points per color, t=2, at most four optimal clusters, and integer distances up to 10; compute the minimum-cost degree-constrained subgraph, merge optimal clusters, and for every minimum-switch path test whether the claimed construction yields replacement edges with total weight at most 6 times the sum of the relevant optimal radii. A single instance failing that bound would refute Lemma 4 and hence Theorems 1 and 2.

Watch

Extended reading notes

Core claim

The paper's central claim is that, in any metric space, a (t,k)-fair sum-of-radii instance with red and blue points can be approximated within (144+ε) in polynomial time, and a balanced instance with ℓ≥2 colors within (180+ε). The algorithm first builds a complete bipartite graph between the two color classes, computes a minimum-weight degree-constrained spanning subgraph in which every vertex has degree between 1 and t—a disjoint union of stars—and then clusters the stars themselves using a known (3+ε)-approximation for vanilla sum-of-radii. Because each star is internally balanced, any union of stars is fair. The technical heart is proving that the cost of the clustering induced on the stars is within a constant factor of the optimal fair cost: optimal clusters are merged along edges of the star subgraph into superclusters, and each supercluster's radius is bounded by 8 times (two-color case) or 10 times (multi-color case) the sum of the radii of its constituent optimal clusters. The multi-color bound yields the stated factors after passing through the (3+ε) subroutine and the factor-3 blow-up incurred when expanding each star's points around its center.

Load-bearing premise

The proof depends on an exhaustive case analysis maintaining that, for every minimum-switch path in the auxiliary graph, a small replacement edge set E'_2 exists; if any configuration of the optimal clusters and the star subgraph is missed, the constant factor—and the main theorem—collapses.

Editorial extensions

If this is right

  • Sum-of-radii joins k-center as a clustering objective for which (t,k)-fairness can be enforced in polynomial time with constant-factor guarantees, with no dependence on the balance parameter t in the approximation ratio.
  • The Euclidean version inherits a polynomial-time O(1)-approximation, replacing the previous f(k)·n^{O(1)}-time (1+ε)-approximation.
  • For balanced clustering with ℓ≥2 colors, the (180+ε) result closes the gap in approximation status between sum-of-radii and k-median/k-center in the t=1 case.
  • The star-decomposition and supercluster-merging analysis gives a new template for constrained sum-of-radii problems, potentially useful where only FPT constant-factor algorithms are known.

Reading between the lines

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

  • If the exchange argument admits a cleaner case analysis or a stronger bound on w(E'_2), the 144 and 180 factors could drop substantially; the paper states that it did not optimize constants.
  • The same star-decomposition idea may transfer to fair representational clustering with general group-wise balance bounds, where currently only bi-criteria O(1)-approximations are known; the obstacle would be replacing t-balanced stars with representational stars.
  • A testable consequence is that the minimum-switch-path bound implies a structural separation: any near-optimal fair sum-of-radii solution is captured by a min-cost degree-constrained subgraph, which could inform streaming or dynamic algorithms for fair clustering.
  • One may also probe whether the technique extends to (t,k)-fair k-median/k-means; the paper leaves this open, and the star bound here is tailored to radii rather than point-assignment costs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies (t,k)-fair sum-of-radii clustering, where each cluster must have a red-to-blue ratio within [1/t,t], and the objective is the sum of cluster radii. The main result is a polynomial-time (144+ε)-approximation for two groups, improving on the FPT (6+ε)-approximation of Carta et al. A second result gives a polynomial-time (180+ε)-approximation for balanced clustering with ℓ≥2 groups when t=1. The algorithm first computes a min-cost degree-constrained subgraph (DCS) on the complete bipartite graph between red and blue points, then clusters the resulting stars using the (3+ε)-approximation of Buchem et al. for sum-of-radii. The analysis introduces a supercluster-merging framework and bounds the diameter of the contracted graph G* through minimum-switch paths, using an exchange argument based on the optimality of the DCS. The multi-color case uses per-color perfect matchings and a color-switch path argument.

Significance. Assuming the proof can be repaired, this is a significant result: it provides the first polynomial-time O(1)-approximation for (t,k)-fair sum-of-radii, matching the status of k-center in this fairness model and improving the FPT result of Carta et al. The multi-color t=1 result also matches known polynomial-time constant approximations for k-center and k-median in the balanced setting. The cluster-merging and minimum-switch path technique is a genuine conceptual contribution and the analysis is a real derivation rather than a circular argument. The paper is clearly written at a high level, but the intricate case analysis in Lemmas 6-9 and the accounting in Lemma 12 require very careful verification; one specific gap is identified below.

major comments (2)
  1. [Section 3.4 (Lemma 12)] The proof of Lemma 12 claims that a vertex shared by two structures in S\{π*} must fall into one of three listed cases. The pair {π(0),π(λ+1)} is omitted. In the case 1−b0=bλ+1, the paper does not prove that π(0) and π(λ+1) are vertex-disjoint; Lemma 10 only asserts 0-1-edge-disjointness for this pair, and the constructions via Lemma 8 and Lemma 9 do not by themselves guarantee vertex-disjointness. This is load-bearing: the per-cluster bound “at most three edges of E′2” is what yields w(E′2)≤6·Σ r(C*i) in Lemma 4, which in turn drives the (144+ε) bound. If the bound degraded to four, the overall factor would become 180+ε rather than 144+ε. The authors should either prove vertex-disjointness of π(0) and π(λ+1) in this subcase, or add an explicit argument that a common vertex of π(0) and π(λ+1) still lies in at most three of the structures in S (using the vertex-disjointness of π(0) and π(λ+1) from every πi(h)). Note that the parity argument for the case 1−b0≠bλ+1 is correct, since there b0=bλ+1; the genuine gap is the omitted pair.
  2. [Section 3.4 (Lemma 10)] The last sentence of the proof of Lemma 10 says that “the 0-1-edge-disjointness of π1(h) and π2(h), or π(0) and π(λ+1), follows from our construction in Lemma 6, 7, 8, and 9.” This is too terse: Lemmas 6-9 construct paths and cycles in graphs obtained by deleting various structures, which guarantees edge-disjointness but not vertex-disjointness. In the subcase where π(λ+1) is obtained via Lemma 8 with O=π(0), the returned path may share vertices with O. Please state explicitly which property (vertex-disjointness versus edge-disjointness) is actually needed for Lemma 12 and verify it. This is closely related to the previous comment, but the two issues should be addressed separately so that the proof of Lemma 12 becomes checkable.
minor comments (5)
  1. [Section 3 (Observation 1)] The proof that a min-cost DCS contains no path of length three assumes that removing the middle edge strictly decreases the cost. This requires positive weights on the edges of the path (or an explicit tie-breaking rule such as choosing a minimum-cost DCS with minimum cardinality). Since P1 and P2 are disjoint point sets in a metric, distinct points have positive distance, but this assumption should be stated explicitly for rigor.
  2. [Section 3.4 (Lemma 12)] In the proof of Lemma 12, the case list for a vertex shared by two structures is incomplete, as noted in the major comments. Even if the bound is repairable, the current sentence “if a vertex is shared by two paths ... then it is either on ...” is false as written and should be corrected.
  3. [Section 3 (Corollary 1)] The equality d′(c,S′) = max_{q′∈S′} d(c,q′) is asserted without proof. It is true because the graph G′ includes all metric edges among points of Ω, so any path from c to S′ has length at least max_{q′∈S′} d(c,q′) by triangle inequality, but this deserves a one-sentence justification.
  4. [Section 3.4] There is a typo in the phrase “Two subraphs G1 and G2”; it should read “Two subgraphs G1 and G2.”
  5. [Section 3.7 (Lemma 8)] The 17-case list in Lemma 8 is very hard to verify by hand. A short coverage check or a table showing how the cases partition the space of possibilities would significantly improve the paper's verifiability, especially because Lemma 8 is a load-bearing component of the exchange argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the approximation factor is derived from the optimality of the min-cost DCS against a constructed alternative, with independent external subroutines.

full rationale

I walked the derivation chain from the algorithm to Theorem 1 and Theorem 2. The algorithm computes a min-cost degree-constrained subgraph via Gabow's algorithm (Proposition 1), then forms a metric on stars, and finally invokes the Buchem et al. (3+epsilon)-approximation for vanilla sum-of-radii clustering. The central analysis is Lemma 4, proved by constructing an alternative degree-constrained subgraph (E'\E'1)∪E'2 and using the minimality of H: Lemma 5 shows that w(E'1)≤w(E'2), so the bound on w(E'2) is the only quantity that needs a separate structural proof. No part of the target approximation factor 144+epsilon or 180+epsilon is assumed as an input; it emerges from the constant 6 in Lemma 4 (times 3 for the star-to-point cost conversion, times 8 for the final radius bound, and times the 3+epsilon black box). The claims are not self-definitional: the star-clustering cost bound is obtained by comparing H with a constructed feasible subgraph, not by fitting any parameter to the optimal cost. The cited prior results used as black boxes, Gabow's DCS algorithm and Buchem et al.'s sum-of-radii approximation, are independent external algorithmic results with stated assumptions that do not include the target theorem. The paper's self-citations, e.g., Bandyapadhyay et al. [7] for pairwise fair k-median, are contextual and are not load-bearing for the main proof. The skeptic's concern about a possible parity error in Section 3.4 concerns whether the internal case analysis of Lemmas 6-9 correctly establishes the claimed bound w(E'2)≤6·sum r(C*_i). Even if that concern were valid, it would be a correctness gap in a non-circular proof step, not a circularity: the bound is an intermediate claim to be proved, not an input to the derivation. The paper itself flags the case analysis as 'fairly involved', which is consistent with an independent technical argument rather than a disguised reuse of the conclusion. Accordingly, I find no step in which a prediction or first-principles result is equivalent to its inputs by construction.

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

The central claim rests on standard background: Gabow's min-cost degree-constrained subgraph algorithm, Buchem et al.'s (3+ε)-approximation for sum-of-radii, and metric triangle inequality. The problem definitions supply the fairness constraints and balance assumptions. No free parameters are fitted to data, and no new entities are postulated; the approximation constants are derived from the proof structure.

assumptions (5)
  • standard math Gabow's min-cost DCS algorithm runs in O(|V|^4) and returns an optimal degree-constrained subgraph
    Used in Step 1 to compute H; Proposition 1 cites Gabow [32].
  • standard math Buchem et al.'s algorithm is a (3+ε)-approximation for minimum sum-of-radii with candidate centers in the input set
    Used in Step 3 for clustering Ω'; cited as [18].
  • standard math Metric properties: triangle inequality, shortest-path metric d' is a metric
    Used throughout the cost analysis.
  • domain assumption For multi-color balanced clustering, the groups have equal size |P1|=...=|Pℓ|
    Part of the Balanced sum-of-radii problem definition in Section 2.
  • domain assumption Optimal (t,k)-fair clustering exists and each cluster satisfies the red-blue ratio within [1/t, t]
    Definition of the problem; used in counting arguments in Lemmas 6-9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering." pith.science (2026). https://pith.science/paper/CMPAQQEX

@misc{pith2026250414683,
  author       = {Pith},
  title        = {Pith review of: Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CMPAQQEX}},
  note         = {Machine review of arXiv:2504.14683}
}
abstract

In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most $t$ times and at least $1/t$ times the number of blue points in that cluster. The goal is to compute a fair clustering with at most $k$ clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center and the $k$-median objective, respectively. Recently, Carta et al. studied this problem with the sum-of-radii objective and obtained a $(6+\epsilon)$-approximation with running time $O((k\log_{1+\epsilon}(k/\epsilon))^kn^{O(1)})$, i.e., fixed-parameter tractable in $k$. Here $n$ is the input size. In this work, we design the first polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as $k$-center, that admit polynomial-time $O(1)$-approximations. This result also implies a polynomial-time $O(1)$-approximation for the Euclidean version of the problem, for which an $f(k)\cdot n^{O(1)}$-time $(1+\epsilon)$-approximation was known due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also able to extend our result to any arbitrary $\ell\ge 2$ number of colors when $t=1$. This matches known results for the $k$-center and $k$-median objectives in this case. The significant disparity of sum-of-radii compared to $k$-center and $k$-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.

Figures

Figures reproduced from arXiv: 2504.14683 by the authors.

Figure 1
Figure 1. (Left) Optimal clusters and (bi-chromatic) edges of [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. (Left) π ∗ (1-2-3) is the path corresponding to the clusters 1, 2, 3 and has no switches. Clusters 1, 4, 5, 6, 7 form a hanging cycle and 3, 8, 9, 10 form a path with 0-edges. The edges of E′ 1 are shown using solid lines which are removed. (Right) The new degree-constrained subgraph. The edges of E′ 2 are shown in bold which were added. and 1-to-0 switches) (see [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. (Top) π ∗ is shown using the bold edges and π1 is shown using the dashed edges. (Bottom) π ∗ 1 is shown using the bold edges. if G1 contains a 1-edge (vi , vj ), and G1 and G2 are 0-1-edge-disjoint, then G2 cannot contain the 1-edge (vi , vj ) and the 0-edge (vj , vi). Let j 1 < j2 < . . . < jλ be the indexes of the vertices on π ∗ = {u1, . . . , ul} where the switches occur. Note that j 1 > 1, jλ < l. Denote the sw… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Figure illustrating the construction of E′ 2 for {π ∗} ∪ {π(l)}. The bold (orange) edges are in E′ 1 and the dashed (purple) edges are in E′ 2 . By our construction, the set of edges (E′ \E′ 1 )∪E′ 2 form a valid degree-constrained subgraph of G on the set of vertices …
Figure 5
Figure 5. Figure 5: A special hanging cycle with the special point [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Figure illustrating the two cases (a) vi = vi ′ = uj h and (b) vi = ul , vi ′ = u1 of Lemma 8. Then, there exists a 0-path (resp. 1-path) π1 from vi to a vertex vj in G∗ , such that O, π ∗ , and π1 are 0-1-edge-disjoint and one of the properties (i)-(xvii) below holds.…
Figure 7
Figure 7. Figure 7: Figure illustrating the construction of E′ 2 for a hanging cycle. The bold (orange) edges are in E′ 1 and the dashed (purple) edges are in E′ 2 . C ∗ i C ∗ j [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: Figure illustrating the construction of E′ 2 for a path. The bold (orange) edges are in E′ 1 and the dashed (purple) edges are in E′ 2 . C ∗ j has a red point of degree in H1 at most t − 1. gets reduced by 1. In E′ 2 , we connect the point, say q ′ , of C ∗ i correspon…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. FPT Constant Approximation Algorithms for Colorful Sum of Radii

    cs.CG 2025-06 reject novelty 6.0 of 10

    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.

Reference graph

Works this paper leans on

54 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    Chen, Allen Liu, Sandeep Silwal, Pattara Sukprasert, Ali Vakil- ian, and Fred Zhang

    Anders Aamand, Justin Y. Chen, Allen Liu, Sandeep Silwal, Pattara Sukprasert, Ali Vakil- ian, and Fred Zhang. Constant approximation for individual preference stable clustering. In Advances in Neural Information Processing Systems (NeurIPS) , 2023. 8

    work page 2023

  2. [2]

    Fair clustering via equi- table group representations

    Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equi- table group representations. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAccT), page 504–514, 2021. 8

    work page 2021

  3. [3]

    Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

    Sara Ahmadian and Chaitanya Swamy. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Lan- guages, and Programming (ICALP 2016) , volume 55 of Leibniz International Proceedings in Informati...

    work page 2016

  4. [4]

    A technique for obtaining true approximations for k-center with covering constraints

    Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. In International conference on integer programming and combinatorial optimization , pages 52–65. Springer, 2020. 8

    work page 2020

  5. [5]

    Local search heuristics for k-median and facility location problems

    Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544–562, 2004. 2

    work page 2004

  6. [6]

    Scalable fair clustering

    Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning , pages 405–413,

    work page

  7. [7]

    A polynomial- time approximation for pairwise fair k-median clustering

    Sayan Bandyapadhyay, Eden Chlamt´ aˇ c, Yury Makarychev, and Ali Vakilian. A polynomial- time approximation for pairwise fair k-median clustering. arXiv preprint arXiv:2405.10378 ,

    arXiv

  8. [8]

    A constant approximation for colorfulk-center

    Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi Varadarajan. A constant approximation for colorfulk-center. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. 8

    work page 2019

Show all 54 references
  1. [9]

    FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii

    Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, 46 SoCG 2023, June...

    2023

  2. [10]

    Varadarajan

    Sayan Bandyapadhyay and Kasturi R. Varadarajan. Approximate clustering via metric par- titioning. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Com- putation, ISAAC 2016, December 12-14, 2016, Sydney, Australia , volume 64 of LIPIcs, pages 15:1–15:13...

    2016 doi

  3. [11]

    Novel properties of hierar- chical probabilistic partitions and their algorithmic applications

    Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Novel properties of hierar- chical probabilistic partitions and their algorithmic applications. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1724–1767. IEEE, 2024. 2, 3

    2024

  4. [12]

    Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants

    Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, and Alon Hovav. Improved fixed-parameter bounds for min-sum-radii and diameters k-clustering and their fair variants. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 39, pages 15481–15488, 2025. 3

    2025

  5. [13]

    Salavatipour

    Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. Algorithmica, 73(1):143–165, 2015. doi:10.1007/s00453-014-9907-3. 2

    2015 doi

  6. [14]

    Fair algorithms for clustering

    Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems, pages 4954–4965, 2019. 3, 4

    2019

  7. [15]

    On the cost of essentially fair clusterings

    Ioana O Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens R¨ osner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Approxi- mation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (AP- PROX/RANDOM 2019). ...

    2019

  8. [16]

    Fair clustering with multiple colors

    Matteo B¨ ohm, Adriano Fazzone, Stefano Leonardi, and Chris Schwiegelshohn. Fair clustering with multiple colors. arXiv preprint arXiv:2002.07892 , 2020. 3, 4

    2002 arXiv

  9. [17]

    Fairness, semi- supervised learning, and more: A general framework for clustering with stochastic pairwise constraints

    B Brubach, D Chakrabarti, J Dickerson, A Srinivasan, and L Tsepenekas. Fairness, semi- supervised learning, and more: A general framework for clustering with stochastic pairwise constraints. In Proc. Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI) , 2021. 8

    2021

  10. [18]

    A (3 + ϵ)- approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds

    Moritz Buchem, Katja Ettmayr, Hugo KK Rosado, and Andreas Wiese. A (3 + ϵ)- approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA...

    2024

  11. [19]

    FPT Ap- proximations for Fairk-Min-Sum-Radii

    Lena Carta, Lukas Drexler, Annika Hennes, Clemens R¨ osner, and Melanie Schmidt. FPT Ap- proximations for Fairk-Min-Sum-Radii. In Juli´ an Mestre and Anthony Wirth, editors,35th In- ternational Symposium on Algorithms and Computation (ISAAC 2024) , volume 322 of Leibniz Intern...

    2024 doi

  12. [20]

    Clustering to minimize the sum of cluster diameters

    Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. , 68(2):417–441, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003. 07.014, doi:10.1016/j.jcss.2003.07.014. 2 47

    2004 doi

  13. [21]

    Matroid and knapsack center problems

    Danny Z Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27–52, 2016. 8

    2016

  14. [22]

    Parameterized approximation algorithms for sum of radii clustering and variants

    Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20666–20673, 2024. 2, 3, 4

    2024

  15. [23]

    Proportionally fair clustering

    Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In International Conference on Machine Learning , pages 1032–1041, 2019. 8

    2019

  16. [24]

    Fair clustering through fairlets

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems , pages 5029–5037,

  17. [25]

    How to solve fair k-center in massive data models

    Ashish Chiplunkar, Sagar Kale, and Sivaramakrishnan Natarajan Ramamoorthy. How to solve fair k-center in massive data models. In Proceedings of the International Conference on Machine Learning (ICML), pages 1877–1886, 2020. 8

    2020

  18. [26]

    Approximating fair clustering with cascaded norm objectives

    Eden Chlamt´ aˇ c, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2664–2683, 2022. 8

    2022

  19. [27]

    Fair representation clustering with several protected classes

    Zhen Dai, Yury Makarychev, and Ali Vakilian. Fair representation clustering with several protected classes. In FAccT ’22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21 - 24, 2022 , pages 814–823. ACM, 2022. 3

    2022

  20. [28]

    Marathe, S

    Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Nord. J. Comput., 7(3):185–203, 2000. 8

    2000

  21. [29]

    Ap- proximating fair k-min-sum-radii in euclidean space

    Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, and Julian Wargalla. Ap- proximating fair k-min-sum-radii in euclidean space. In International Workshop on Approxi- mation and Online Algorithms , pages 119–133. Springer, 2023. 1, 3

    2023

  22. [30]

    Fpt approximations for capacitated sum of radii and diameters

    Arnold Filtser and Ameet Gadekar. Fpt approximations for capacitated sum of radii and diameters. arXiv preprint arXiv:2409.04984 , 2024. 2, 4

    2024 arXiv

  23. [31]

    Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters

    Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algo- rithms (ESA 2022) , vo...

    2022

  24. [32]

    An efficient reduction technique for degree-constrained subgraph and bidi- rected network flow problems

    Harold N Gabow. An efficient reduction technique for degree-constrained subgraph and bidi- rected network flow problems. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 448–456, 1983. 5, 9

    1983

  25. [33]

    Mehrdad Ghadiri, Samira Samadi, and Santosh S. Vempala. Socially fair k-means clustering. In Madeleine Clare Elish, William Isaac, and Richard S. Zemel, editors, FAccT ’21: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event / Toronto, Canada, Marc...

    2021

  26. [34]

    Constant-factor approximation al- gorithms for socially fair k-clustering

    Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala. Constant-factor approximation al- gorithms for socially fair k-clustering. arXiv preprint arXiv:2206.11210 , 2022. 8

    2022 arXiv

  27. [35]

    Pirwani, and Kasturi R

    Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484–498, 2010. doi: 10.1007/s00453-009-9282-7. 2

    2010 doi

  28. [36]

    Pirwani, and Kasturi R

    Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On clustering to minimize the sum of radii. SIAM J. Comput. , 41(1):47–60, 2012. doi: 10.1137/100798144. 2

    2012 doi

  29. [37]

    Clustering to minimize the maximum intercluster distance

    Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. 2

    1985

  30. [38]

    Which lp norm is the fairest? approximations for fair facility location across all “ p”, 2022

    Swati Gupta, Jai Moondra, and Mohit Singh. Which lp norm is the fairest? approximations for fair facility location across all “ p”, 2022. arXiv:2211.14873. 8

    2022 arXiv

  31. [39]

    Optimal broadcast domination in polynomial time

    Pinar Heggernes and Daniel Lokshtanov. Optimal broadcast domination in polynomial time. Discret. Math., 306(24):3267–3280, 2006. doi:10.1016/j.disc.2006.06.013. 2

    2006 doi

  32. [40]

    Dynamic clustering to minimize the sum of radii

    Monika Henzinger, Dariusz Leniowski, and Claire Mathieu. Dynamic clustering to minimize the sum of radii. Algorithmica, 82(11):3183–3194, 2020. doi:10.1007/s00453-020-00721-7. 8

    2020 doi

  33. [41]

    Approximation algorithms for fair range clustering

    Sedjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. In International Conference on Machine Learning , pages 13270–13284. PMLR, 2023. 8

    2023

  34. [42]

    Varadarajan

    Tanmay Inamdar and Kasturi R. Varadarajan. Capacitated sum-of-radii clustering: An FPT approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference...

    2020 doi

  35. [43]

    FPT approximation for capacitated sum of radii

    Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA , volume 287 of LIPIcs, pages...

    2024

  36. [44]

    Fair colorfulk-center clustering

    Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorfulk-center clustering. In International Conference on Integer Programming and Combinatorial Optimization, pages 209–222. Springer,

  37. [45]

    A center in your neighborhood: Fairness in facility location

    Christopher Jung, Sampath Kannan, and Neil Lutz. A center in your neighborhood: Fairness in facility location. In Proceedings of the Symposium on Foundations of Responsible Computing (FORC), page 5:1–5:15, 2020. 8

    2020

  38. [46]

    Mount, Nathan S

    Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89–112, 2004. 2 49

    2004

  39. [47]

    Fair k-center clustering for data summarization

    Matth¨ aus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In 36th International Conference on Machine Learning, ICML 2019 , pages 5984–6003. International Machine Learning Society (IMLS), 2019. 8

    2019

  40. [48]

    Constant approximation for k-median and k-means with outliers via iterative rounding

    Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 646–659, 2018. 8

    2018

  41. [49]

    Approximation algorithms for socially fair clustering

    Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory (COLT), pages 3246–3264. PMLR, 2021. 8

    2021

  42. [50]

    Proportionally fair clustering revisited

    Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In International Collo- quium on Automata, Languages, and Programming (ICALP) , 2020. 8

    2020

  43. [51]

    Better algorithms for individually fair k- clustering

    Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k- clustering. Advances in Neural Information Processing Systems (NeurIPS) , 34:13340–13351,

  44. [52]

    Computing a many-to-many matching with de- mands and capacities between two sets using the hungarian algorithm.Journal of mathematics, 2023(1):7761902, 2023

    Fatemeh Rajabi-Alni and Alireza Bagheri. Computing a many-to-many matching with de- mands and capacities between two sets using the hungarian algorithm.Journal of mathematics, 2023(1):7761902, 2023. 9

    2023

  45. [53]

    Fair coresets and streaming algorithms for fair k-means

    Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In International Workshop on Approximation and Online Algo- rithms, pages 232–251. Springer, 2019. 3

    2019

  46. [54]

    Improved approximation algorithms for individually fair clustering

    Ali Vakilian and Mustafa Yal¸ cıner. Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 8758–8779. PMLR, 2022. 8 50

    2022

Pith tools

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