pith. sign in

arxiv: 2602.05476 · v2 · submitted 2026-02-05 · 💻 cs.DS

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives

Ameet Gadekar This is my paper

Pith reviewed 2026-05-16 07:21 UTC · model grok-4.3

classification 💻 cs.DS
keywords fair clusteringsum of radiiapproximation algorithmsfixed parameter tractableoutlierssymmetric normsclustering with constraints
0
0 comments X

The pith

The fair sum of radii clustering problem with outliers admits a (3+ε)-approximation in FPT time parameterized by k.

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

This paper introduces an algorithm for placing k balls to cover most points while satisfying fairness constraints on group representations and minimizing the sum of radii. The algorithm runs in time that is fixed-parameter tractable in k, meaning it is efficient when the number of clusters is small. It achieves a (3+ε) approximation ratio and generalizes to objectives defined by any monotone symmetric norm of the radii. The approach also produces a list of candidates that approximates well for every such norm without knowing which one will be used.

Core claim

The paper establishes that an iterative ball-finding framework can uncover a structural trichotomy in any optimal clustering for the fair sum of radii with outliers. This trichotomy enables the direct construction of a fair solution that covers all but z outliers, yielding a (3+ε)-approximation that holds for any fixed monotone symmetric norm and is tight under the Gap-ETH assumption.

What carries the argument

Iterative ball-finding framework that identifies a structural trichotomy in the optimal clustering to build fair solutions while handling outliers.

If this is right

  • The same (3+ε) guarantee applies to any monotone symmetric norm objective.
  • The algorithm outputs a small list of candidates that is oblivious to the specific norm.
  • The techniques extend to the fair-range setting with both lower and upper bounds on group representations.
  • The approximation ratio is tight assuming Gap-ETH.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This structural trichotomy may help design FPT approximations for other fair clustering problems like k-median or k-means.
  • Practitioners could use the candidate list to optimize for custom fairness norms after a single run.
  • Similar ball-finding ideas could apply to non-metric distances if the trichotomy still holds in some relaxed form.

Load-bearing premise

The distances between points satisfy the triangle inequality and fairness is defined via group-based lower and upper bounds.

What would settle it

A concrete metric instance and group constraints where every fair clustering with at most z outliers has sum of radii more than (3+ε) times the optimum, or a reduction showing Gap-ETH violation if such an algorithm exists.

Figures

Figures reproduced from arXiv: 2602.05476 by Ameet Gadekar.

Figure 1
Figure 1. Figure 1: Flow of the iterative ball-finding algorithm for colorful SoR with outliers. Lightly shaded [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The rectangle represents the full point set, while the colored discs correspond to the optimal clusters, with the remaining area representing outliers. The relative sizes of the discs illustrate the densities of the clusters. For simplicity, the center color classes are not shown. The iterative ball-finding subroutine is invoked for the densest uncovered optimal cluster, which is green (π ∗ 1 ), and some b… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the two-light-balls case for the example of [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
read the original abstract

The sum of radii problem is a classical clustering problem in which, given a set $X$ of points and an integer $k$, the goal is to place $k$ balls that cover $X$ while minimizing the sum of their radii. Recent work has focused on incorporating modern constraints such as fairness and robustness, motivated by biased and noisy data. We study the fair sum of radii with outliers problem, where the chosen centers must satisfy group-based representation constraints while allowing up to $z$ points to be excluded. We present a $(3+\epsilon)$-approximation algorithm that runs in fixed-parameter tractable time parameterized by $k$. Our framework extends to the more general setting where the objective is a monotone symmetric norm of the radii, achieving a $(3+\epsilon)$-approximation for any fixed norm; this guarantee is tight under Gap-ETH. Moreover, the algorithm is oblivious to the choice of norm: it outputs a small list of candidate solutions such that, for every monotone symmetric norm $f$, the list contains a $(3+\epsilon)$-approximate solution under $f$. Our approach is based on a novel iterative ball-finding framework that uncovers a structural trichotomy in the optimal clustering, enabling us to directly construct fair solutions while handling outliers. Finally, we extend our techniques to the more general fair-range setting, where each group is subject to both lower and upper bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a (3+ε)-approximation algorithm for the fair sum-of-radii problem with outliers that runs in FPT time parameterized by k. Centers must obey group-based fairness constraints while allowing up to z outliers. The framework extends to any fixed monotone symmetric norm of the radii, producing an oblivious list of O(1) candidate solutions that contains a (3+ε)-approximate solution for every such norm; the guarantee is tight under Gap-ETH. The algorithm relies on an iterative ball-finding procedure that establishes a structural trichotomy in optimal solutions, and the techniques are further extended to the fair-range setting with both lower and upper group bounds.

Significance. If the central claims hold, the result is a meaningful advance in fair and robust clustering. It supplies the first FPT approximation for this combination of fairness, outliers, and general-norm objectives, with an oblivious candidate-list property that is algorithmically useful. The matching Gap-ETH lower bound and the clean reliance on the metric property plus explicit group bounds are additional strengths.

minor comments (2)
  1. [Abstract] Abstract: the statement that the algorithm is 'oblivious to the choice of norm' should be accompanied by a brief parenthetical clarifying that the list size is independent of the norm (or state the dependence explicitly).
  2. [Introduction] The manuscript should include a short paragraph in the introduction or preliminaries that explicitly lists the group fairness constraints (lower/upper representation bounds) and the outlier parameter z, so that the trichotomy argument can be read without cross-referencing the problem definition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation for minor revision. The referee correctly identifies the (3+ε)-FPT approximation, the extension to monotone symmetric norms, the oblivious candidate list, the Gap-ETH tightness, and the extension to the fair-range setting.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives its (3+ε)-FPT approximation for fair sum-of-radii with outliers (and the oblivious extension to any fixed monotone symmetric norm) from an iterative ball-finding procedure that produces a structural trichotomy. This construction relies solely on the triangle inequality of the input metric and the explicit group-based lower/upper representation bounds; no quantity is defined in terms of itself, no parameter is fitted to a subset and then renamed as a prediction, and no load-bearing step reduces to a self-citation or prior ansatz by the same authors. The hardness claim under Gap-ETH is imported as an external lower bound rather than derived internally. The algorithm therefore remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard metric assumption and the definition of monotone symmetric norms; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption The distance function on the point set satisfies the triangle inequality.
    Invoked implicitly for all radius and covering arguments in sum-of-radii clustering.
  • standard math Monotone symmetric norms are closed under certain operations used in the analysis.
    Used to extend the (3+ε) guarantee from sum to arbitrary monotone symmetric norms.

pith-pipeline@v0.9.0 · 5550 in / 1489 out tokens · 27687 ms · 2026-05-16T07:21:24.384759+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    Parameter- ized approximation schemes for clustering with general norm objectives

    Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, D´ aniel Marx, Roohani Sharma, and Joachim Spoerhase. Parameter- ized approximation schemes for clustering with general norm objectives. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, Novem- ber 6-9, 202...

    work page 2023

  2. [2]

    Clustering with- out over-representation

    Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering with- out over-representation. InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19, page 267–275, New York, NY, USA, 2019. Association for Computing Machinery. 1

    work page 2019

  3. [3]

    Minimum-cost coverage of point sets by disks

    Helmut Alt, Esther M Arkin, Herv´ e Br¨ onnimann, Jeff Erickson, S´ andor P Fekete, Christian Knauer, Jonathan Lenchner, Joseph SB Mitchell, and Kim Whittlesey. Minimum-cost coverage of point sets by disks. InProceedings of the twenty-second annual symposium on Computational geometry, pages 449–458, 2006. 2

    work page 2006

  4. [4]

    A simple combinatorial algorithm for robust matroid center

    Georg Anegg, Laura Vargas Koch, and Rico Zenklusen. A simple combinatorial algorithm for robust matroid center. In Telikepalli Kavitha and Kurt Mehlhorn, editors,2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023, pages 96–102. SIAM, 2023. 1

    work page 2023

  5. [5]

    The hardness of approximation of euclideank-means

    Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclideank-means. In31st International Symposium on Com- putational Geometry (SoCG’15). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. 1

    work page 2015

  6. [6]

    Improved FPT approximation for sum of radii clustering with mergeable constraints

    Sayan Bandyapadhyay and Tianzhi Chen. Improved FPT approximation for sum of radii clustering with mergeable constraints. In Alina Ene and Eshan Chattopadhyay, editors,Ap- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2025, Berkeley, CA, USA, August 11-13, 2025, LIPIcs, pages 23:1– 23:17. Schloss Dagst...

    work page 2025

  7. [7]

    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 (SoCG 2023), volume 258 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:1...

    work page 2023

  8. [8]

    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 Toby Walsh, Julie Shah, and Zico Kolter, editors,Thirty-Ninth AAAI Conference on Artificial Intelligence, Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence, Fi...

    work page 2025

  9. [9]

    Fair algorithms for clustering

    Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alch´ e-Buc, Emily B. Fox, and Roman Garnett, editors,Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, Neur...

    work page 2019

  10. [10]

    Schmidt, and Melanie Schmidt

    Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens R¨ osner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Dimitris Achliop- tas and L´ aszl´ o A. V´ egh, editors,Approximation, Randomization, and Combinatorial Opti- mization. Algorithms and Techniques, APPROX/RANDOM 2019, Massachusetts Institu...

    work page 2019

  11. [11]

    Faster algorithms for the constrained k-means problem.Theory of Computing Systems, 62(1):93–115, 2018

    Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem.Theory of Computing Systems, 62(1):93–115, 2018. 3

    work page 2018

  12. [12]

    Fair clustering with multiple colors.CoRR, abs/2002.07892, 2020

    Matteo B¨ ohm, Adriano Fazzone, Stefano Leonardi, and Chris Schwiegelshohn. Fair clustering with multiple colors.CoRR, abs/2002.07892, 2020. 1

    work page arXiv 2002

  13. [13]

    Moritz Buchem, Katja Ettmayr, Hugo K. K. Rosado, and Andreas Wiese. A (3 +ε)- approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In David P. Woodruff, editor,Proceedings of the 2024 ACM- SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1738...

    work page 2024

  14. [14]

    FPT approximations for fair k-min-sum-radii

    Lena Carta, Lukas Drexler, Annika Hennes, Clemens R¨ osner, and Melanie Schmidt. FPT approximations for fair k-min-sum-radii. In Juli´ an Mestre and Anthony Wirth, editors,35th International Symposium on Algorithms and Computation, ISAAC 2024, Sydney, Australia, December 8-11, 2024, LIPIcs, pages 16:1–16:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Infor-...

    work page 2024

  15. [15]

    Generalized center problems with outliers

    Deeparnab Chakrabarty and Maryam Negahbani. Generalized center problems with outliers. ACM Trans. Algorithms, 15(3):41:1–41:14, 2019. 1

    work page 2019

  16. [16]

    Approximation algorithms for minimum norm and ordered optimization problems

    Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. InProceedings of the 51st Annual ACM SIGACT Sym- posium on Theory of Computing, STOC 2019, page 126–137, New York, NY, USA, 2019. Association for Computing Machinery. 2

    work page 2019

  17. [17]

    Mount, and Giri Narasimhan

    Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In S. Rao Kosaraju, editor,Proceedings of the Twelfth Annual 23 Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 642–651. ACM/SIAM, 2001. 3, 4, 6

    work page 2001

  18. [18]

    Clustering to minimize the sum of cluster diameters

    Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and System Sciences, 68(2):417–441, 2004. Special Issue on STOC 2001. 1

    work page 2004

  19. [19]

    Parameterized approximation al- gorithms for sum of radii clustering and variants

    Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation al- gorithms for sum of radii clustering and variants. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors,Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence,...

    work page 2024

  20. [20]

    Fair clustering through fairlets

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors,Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 20...

    work page 2017

  21. [21]

    Approximating fair clustering with cascaded norm objectives

    Eden Chlamt´ ac, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2664–2683. SIAM, 2022. 2

    work page 2022

  22. [22]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer Publish- ing Company, Incorporated, 1st edition, 2015. 14

    work page 2015

  23. [23]

    A unified framework for clustering constrained data without locality property.Algorithmica, 82(4):808–852, 2020

    Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property.Algorithmica, 82(4):808–852, 2020. 3

    work page 2020

  24. [24]

    48550/ARXIV.2310.02130

    Lukas Drexler, Jan H¨ ockendorff, Joshua K¨ onen, and Kevin Schewior. Clustering graphs of bounded treewidth to minimize the sum of radius-dependent costs.CoRR, abs/2310.02130,

    work page arXiv

  25. [25]

    Improved PTAS for the constrained k-means problem.J

    Qilong Feng, Jiaxin Hu, Neng Huang, and Jianxin Wang. Improved PTAS for the constrained k-means problem.J. Comb. Optim., 37(4):1091–1110, 2019. 3

    work page 2019

  26. [26]

    FPT approximations for capacitated sum of radii and diameters.CoRR, abs/2409.04984, 2024

    Arnold Filtser and Ameet Gadekar. FPT approximations for capacitated sum of radii and diameters.CoRR, abs/2409.04984, 2024. 9, 10

    work page arXiv 2024

  27. [27]

    Fair clustering for data summariza- tion: Improved approximation algorithms and complexity insights

    Ameet Gadekar, Aristides Gionis, and Suhas Thejaswi. Fair clustering for data summariza- tion: Improved approximation algorithms and complexity insights. In Guodong Long, Michale Blumestein, Yi Chang, Liane Lewin-Eytan, Zi Helen Huang, and Elad Yom-Tov, editors,Pro- ceedings of the ACM on Web Conference 2025, WWW 2025, Sydney, NSW, Australia, 28 April 202...

    work page 2025

  28. [28]

    Capacitated fair-range clustering: Hardness and approx- imation algorithms.CoRR, abs/2505.15905, 2025

    Ameet Gadekar and Suhas Thejaswi. Capacitated fair-range clustering: Hardness and approx- imation algorithms.CoRR, abs/2505.15905, 2025. 3 24

    work page arXiv 2025

  29. [29]

    When a worse approximation factor gives better performance: a 3- approximation algorithm for the vertex k-center problem.J

    Jesus Garcia-Diaz, Jairo Javier Sanchez-Hernandez, Ricardo Menchaca-Mendez, and Rolando Menchaca-M´ endez. When a worse approximation factor gives better performance: a 3- approximation algorithm for the vertex k-center problem.J. Heuristics, 23(5):349–366, 2017. 1

    work page 2017

  30. [30]

    Pirwani, and Kasturi Varadarajan

    Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan. On metric clustering to minimize the sum of radii.Algorithmica, 57(3):484–498, jul 2010. 1

    work page 2010

  31. [31]

    Clustering to minimize the maximum intercluster distance.Theoretical computer science, 38:293–306, 1985

    Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance.Theoretical computer science, 38:293–306, 1985. 1

    work page 1985

  32. [32]

    Harris, Thomas W

    David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. A lottery model for center-type problems with outliers.ACM Trans. Algorithms, 15(3):36:1–36:25, 2019. 1

    work page 2019

  33. [33]

    Herold, Evangelos Kipouridis, and Joachim Spoerhase

    Martin G. Herold, Evangelos Kipouridis, and Joachim Spoerhase. Clustering to minimize cluster-aware norm objectives. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 255–287. SIAM, 2025. 2

    work page 2025

  34. [34]

    Herold, Evangelos Kipouridis, and Joachim Spoerhase

    Martin G. Herold, Evangelos Kipouridis, and Joachim Spoerhase. A broader view on cluster- ing under cluster-aware norm objectives. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 758–793. SIAM, 2026. 2

    work page 2026

  35. [35]

    A best possible heuristic for the k-center problem

    Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180–184, 1985. 1

    work page 1985

  36. [36]

    Approximation algorithms for fair range clustering

    S` edjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara En- gelhardt, Sivan Sabato, and Jonathan Scarlett, editors,International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learni...

    work page 2023

  37. [37]

    Capacitated Sum-Of-Radii Clustering: An FPT Approximation

    Tanmay Inamdar and Kasturi Varadarajan. Capacitated Sum-Of-Radii Clustering: An FPT Approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors,28th An- nual European Symposium on Algorithms (ESA 2020), volume 173 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 62:1–62:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl...

    work page 2020

  38. [38]

    Nguyen, and Thy Dinh Nguyen

    Matthew Jones, Huy L. Nguyen, and Thy Dinh Nguyen. Fair k-centers via maximum matching. InProceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 ofProceedings of Machine Learning Research, pages 4940–4949. PMLR, 2020. 1, 4

    work page 2020

  39. [39]

    Fair k-center clustering for data summarization

    Matth¨ aus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, pages 3448–3457. PMLR,

    work page 2019

  40. [40]

    FPT constant approximation algorithms for colorful sum of radii.CoRR, abs/2506.13191, 2025

    Shuilian Liu, Gregory Gutin, Yicheng Xu, and Yong Zhang. FPT constant approximation algorithms for colorful sum of radii.CoRR, abs/2506.13191, 2025. 2

    work page arXiv 2025

  41. [41]

    A primal-dual approximation algorithm for the k- prize-collecting minimum power cover problem.Optimization Letters, 16(8):2373–2385, 2022

    Xiaofei Liu, Weidong Li, and Runtao Xie. A primal-dual approximation algorithm for the k- prize-collecting minimum power cover problem.Optimization Letters, 16(8):2373–2385, 2022. 2

    work page 2022

  42. [42]

    Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem)

    Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 62–81, USA, 2020. Society for Industrial and Applied Mathematics. 3

    work page 2020

  43. [43]

    Proportionally fair clustering revisited

    Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors,47th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2020, Saarbr¨ ucken, Germany (Virtual Conference), July 8-11, 2020, LIPIcs, pages 85:1–85:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2020. 1

    work page 2020

  44. [44]

    Partitioning points and graphs to minimize the maximum or the sum of diameters

    Clyde Monma and Subhash Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. InGraph Theory, Combinatorics and Applications (Proc. 6th Internat. Conf. Theory Appl. Graphs), volume 2, pages 899–912, 1989. 1

    work page 1989

  45. [45]

    Fair range k-center.CoRR, abs/2207.11337, 2022

    Huy Le Nguyen, Thy Dinh Nguyen, and Matthew Jones. Fair range k-center.CoRR, abs/2207.11337, 2022. 3

    work page arXiv 2022

  46. [46]

    Privacy preserving clustering with constraints

    Clemens R¨ osner and Melanie Schmidt. Privacy preserving clustering with constraints. In Ioannis Chatzigiannakis, Christos Kaklamanis, D´ aniel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, LIPIcs, pages 96:1–96:14. Schloss Dagstuhl - Leibniz-...

    work page 2018

  47. [47]

    Diversity-aware clustering: Computational complexity and approximation algorithms.CoRR, abs/2401.05502,

    Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis. Diversity-aware clustering: Computational complexity and approximation algorithms.CoRR, abs/2401.05502,

    work page arXiv

  48. [48]

    Clustering with fair-center representation: Parameterized approximation algorithms and heuristics

    Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. Clustering with fair-center representation: Parameterized approximation algorithms and heuristics. In Aidong Zhang and Huzefa Rangwala, editors,KDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022, pages 1749–1759. ACM, 2022. 1

    work page 2022

  49. [49]

    Parame- terized approximation schemes for fair-range clustering

    Zhen Zhang, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, and Qilong Feng. Parame- terized approximation schemes for fair-range clustering. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Infor- ...

    work page 2024