pith. sign in

arxiv: 2512.04614 · v2 · submitted 2025-12-04 · 💻 cs.DS

On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Han Dai , Shi Li , Sijin Peng This is my paper

Pith reviewed 2026-05-17 01:58 UTC · model grok-4.3

classification 💻 cs.DS
keywords approximation algorithmsfixed-parameter tractabilityk-clusteringcapacitated clusteringgeneral normtop-cn norm
0
0 comments X

The pith

A unified framework yields tight (3+ε)-approximations for general-norm capacitated k-clustering in FPT time parameterized by k and ε.

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

The paper develops FPT-time approximation algorithms for minimum-norm k-clustering problems parameterized by the number of facilities k. It establishes a tight (3+ε)-approximation for the capacitated general-norm k-clustering problem, extending a result previously known only for the capacitated k-median case. As a special case it gives an FPT-time 3-approximation for capacitated k-center, improving on the prior polynomial-time ratio of 9. For the uncapacitated top-cn norm variant it achieves a tight (1 + 2/(e c) + ε) guarantee when c lies in (1/e, 1], and the same framework produces a tight (3, 1 + 2/e + ε) bicriteria approximation for the joint (k-center, k-median) objective.

Core claim

The central claim is that a single algorithmic template—computing a (1+ε)-approximate solution with O(k log n / ε) facilities via LP rounding, sampling a small set of client representatives, guessing a few pivots from the combined set together with radius information, and solving the problem exactly on those guesses—produces the stated tight approximation ratios for both the capacitated general-norm case and the top-cn norm case.

What carries the argument

The unified framework of LP rounding to O(k log n / ε) facilities, sampling client representatives, guessing pivots from S ∪ R and radius information, and solving exactly on the guesses.

If this is right

  • The result immediately gives an FPT-time 3-approximation for capacitated k-center.
  • It yields a tight (1 + 2/(e c) + ε)-approximation for top-cn norm k-clustering when c ∈ (1/e, 1].
  • The framework extends to a tight (3, 1 + 2/e + ε) bicriteria approximation for the (k-center, k-median) problem in FPT time.
  • The same template is expected to produce further tight FPT approximations for other k-clustering objectives.

Where Pith is reading between the lines

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

  • The guessing step on pivots and radii may transfer to other parameterized geometric optimization problems that currently lack tight FPT approximations.
  • Extending the same sampling and guessing technique to objectives that combine multiple norms could produce new bicriteria results without increasing the parameterization.

Load-bearing premise

The LP rounding plus sampling plus exact solving on a few guessed pivots and radii actually produces the claimed tight approximation ratios for the general-norm capacitated and top-cn cases.

What would settle it

An instance of capacitated general-norm k-clustering on which the algorithm returns a solution whose cost exceeds (3+ε) times the optimum for sufficiently small ε would show the claimed guarantee does not hold.

Figures

Figures reproduced from arXiv: 2512.04614 by Han Dai, Shi Li, Sijin Peng.

Figure 1
Figure 1. Figure 1: 3 types of connected components of H. In the first type, a type-1 color c is connected to qc. Notice that qc is defined via a representative client pc ∈ R ∩ J¯∗ c . In the second type, we have many type-2 colors c ∈ D connected to their common pc. pc for a type-2 color c is defined via a client j. In the third type, we have many type-2 colors c ∈ D (D′ in the figure to avoid confusion) connected to their c… view at source ↗
read the original abstract

Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm $k$-clustering problems, parameterized by the number $k$ of open facilities. For the capacitated setting, we give a tight $(3+\epsilon)$-approximation for the general-norm capacitated $k$-clustering problem in FPT-time parameterized by $k$ and $\epsilon$. Prior to our work, such a result was only known for the capacitated $k$-median problem [CL, ICALP, 2019]. As a special case, our result yields an FPT-time $3$-approximation for capacitated $k$-center. The problem has not been studied in the FPT-time setting, with the previous best known polynomial-time approximation ratio being 9 [ABCG, MP, 2015]. In the uncapacitated setting, we consider the $top$-$cn$ norm $k$-clustering problem, where the goal of the problem is to minimize the $top$-$cn$ norm of the connection distance vector. Our main result is a tight $\big(1 + \frac 2{ec} + \epsilon\big)$-approximation algorithm for the problem with $c \in \big(\frac1e, 1\big]$. (For the case $c \leq \frac1e$, there is a simple tight $(3+\epsilon)$-approximation.) Our framework can be easily extended to give a tight $\left(3, 1+\frac2e + \epsilon\right)$-bicriteria approximation for the ($k$-center, $k$-median) problem in FPT time, improving the previous best polynomial-time $(4, 8)$ guarantee [AB, WAOA, 2017]. All results are based on a unified framework: computing a $(1+\epsilon)$-approximate solution using $O\left(\frac{k\log n}{\epsilon}\right)$ facilities $S$ via LP rounding, sampling a few client representatives $R$ based on the solution $S$, guessing a few pivots from $S \cup R$ and some radius information on the pivots, and solving the problem using the guesses. We believe this framework can lead to further results on $k$-clustering problems.

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

2 major / 2 minor

Summary. The paper presents a unified framework combining LP rounding, sampling, and guessing of pivots/radii to obtain FPT-time approximation algorithms for k-clustering variants. It claims a tight (3+ε)-approximation for general-norm capacitated k-clustering (parameterized by k and ε), a tight (1 + 2/(e c) + ε)-approximation for uncapacitated top-cn norm k-clustering when c ∈ (1/e, 1], a simple (3+ε) for smaller c, an FPT 3-approximation for capacitated k-center, and a (3, 1 + 2/e + ε) bicriteria result for (k-center, k-median). All results rely on computing an (1+ε)-approximate solution with O(k log n / ε) facilities via LP rounding, sampling client representatives, guessing a small number of pivots and radius information, and solving exactly on the guesses.

Significance. If the guessing procedure is shown to correctly recover the claimed ratios for arbitrary norms under capacities, the results would advance the combination of approximation and FPT techniques for clustering by extending tight ratios beyond the k-median case and providing the first FPT results for capacitated k-center and top-cn norms. The unified framework is a reusable strength that could apply more broadly.

major comments (2)
  1. [§3] §3 (Unified Framework description): The claim that guessing a small number of pivots from S ∪ R together with radius information suffices to obtain a (3+ε) guarantee for arbitrary norms must be supported by an explicit argument showing how the guessed radii approximate the optimal radius vector for the connection-cost vector. General norms can weight arbitrary tails of the sorted distance vector, unlike k-median where averaging suffices; the manuscript needs to bound the number of guesses per pivot (as a function of k and ε) and prove that missing a critical threshold cannot inflate the norm by more than ε under capacity constraints.
  2. [Main theorem for general-norm capacitated k-clustering] Main theorem for general-norm capacitated k-clustering (around the statement of the (3+ε) result): The reduction from the LP solution with O(k log n / ε) facilities to the exact solve on guesses must explicitly handle how capacities interact with the norm when the guessed radii are inexact. The current high-level outline does not rule out that an arbitrary norm could select a different set of connections once capacities are enforced, potentially violating the tightness.
minor comments (2)
  1. [Abstract] The abstract states that the framework 'can lead to further results' without specifying which; this is minor but could be moved to the conclusion or removed to keep the abstract focused on proven claims.
  2. [Introduction / Preliminaries] Notation for the top-cn norm and the parameter c should be defined at first use with a brief reminder of the norm definition to aid readers unfamiliar with the variant.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below. We agree that additional explicit arguments are needed to strengthen the presentation and will revise the paper to include them.

read point-by-point responses

  1. Referee: [§3] §3 (Unified Framework description): The claim that guessing a small number of pivots from S ∪ R together with radius information suffices to obtain a (3+ε) guarantee for arbitrary norms must be supported by an explicit argument showing how the guessed radii approximate the optimal radius vector for the connection-cost vector. General norms can weight arbitrary tails of the sorted distance vector, unlike k-median where averaging suffices; the manuscript needs to bound the number of guesses per pivot (as a function of k and ε) and prove that missing a critical threshold cannot inflate the norm by more than ε under capacity constraints.

    Authors: We agree that the current high-level description in §3 would benefit from a more explicit argument tailored to arbitrary norms. In the revised manuscript we will expand §3 with a dedicated lemma that (i) recalls that a general norm is a non-decreasing function of the sorted connection-cost vector, (ii) shows that the (1+ε)-approximate LP solution with O(k log n / ε) facilities yields a discretization of candidate radii into O(k/ε) thresholds per pivot (an FPT number of guesses overall), and (iii) proves that any missed critical threshold changes the sorted vector by a multiplicative (1+ε) factor on any tail. Because the norm is Lipschitz with respect to such perturbations, the total inflation is at most ε. The same discretization argument continues to hold when capacities are present: the exact solve on the guessed pivots and radii respects the capacity constraints exactly, while the client sampling ensures that the mass of each client group is preserved up to (1+ε), so the selected integral assignment cannot deviate from the optimal one by more than the claimed factor in the sorted vector. revision: yes

  2. Referee: [Main theorem for general-norm capacitated k-clustering] Main theorem for general-norm capacitated k-clustering (around the statement of the (3+ε) result): The reduction from the LP solution with O(k log n / ε) facilities to the exact solve on guesses must explicitly handle how capacities interact with the norm when the guessed radii are inexact. The current high-level outline does not rule out that an arbitrary norm could select a different set of connections once capacities are enforced, potentially violating the tightness.

    Authors: We acknowledge that the interaction between inexact radii and capacity constraints requires a more detailed treatment in the proof of the main theorem. In the revision we will insert a new subsection that explicitly analyzes the reduction. We will prove that the guessed radii are within a (1+ε) multiplicative factor of the optimal radii at every relevant scale for the norm. When the exact solver enforces capacities on these guessed radii, the resulting connection-cost vector remains close in sorted order to the vector produced by the optimal solution under the true radii; the difference is bounded by the sampling error plus the discretization error. Because every general norm depends only on the sorted distances and is monotonic, this closeness preserves the (3+ε) guarantee. We will also add a short argument showing that any alternative connection set chosen under the inexact radii cannot increase the norm beyond the target ratio, since the LP solution already satisfies a relaxed capacity constraint and the sampled representatives capture the bulk of the client mass. revision: yes

Circularity Check

0 steps flagged

No significant circularity; framework presented as independent construction

full rationale

The paper's central results rest on a unified framework of (1+ε)-approximate LP rounding to O(k log n/ε) facilities S, sampling client representatives R, guessing a small number of pivots from S∪R plus radius information, and exact solving on the guesses. This is described as a new construction that extends the known (3+ε) result for capacitated k-median to general-norm capacitated k-clustering and top-cn norms. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided abstract or framework outline. The derivation is self-contained against external benchmarks such as standard LP rounding and enumeration, with prior citations (e.g., [CL, ICALP 2019]) serving as independent support rather than a reduction chain. The guessing step for radii is claimed to suffice for arbitrary norms but is not shown to reduce tautologically to the input LP solution.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard techniques from approximation algorithms and FPT; no new free parameters beyond the explicit approximation slack ε, no invented entities, and axioms are background results on LP relaxations and rounding.

axioms (1)
  • standard math Linear programming relaxations for k-clustering admit (1+ε)-approximate integral solutions via rounding when extra facilities are allowed.
    Invoked in the description of the first step of the unified framework.

pith-pipeline@v0.9.0 · 5740 in / 1412 out tokens · 41620 ms · 2026-05-17T01:58:18.644528+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering

    cs.DS 2026-05 unverdicted novelty 7.0

    k-MSR is W[2]-hard parameterized by k with no EPAS unless W[2]=FPT, and admits an FPT (8/3+ε)-approximation under mergeable constraints, improving prior (4+ε) bounds.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    Approximation algorithms for hard capacitatedk-facility location problems.European Journal of Operational Research, 242(2):358– 368, 2015

    Karen Aardal, Pieter L.van den Berg, Dion Gijswijt, and Shanfei Li. Approximation algorithms for hard capacitatedk-facility location problems.European Journal of Operational Research, 242(2):358– 368, 2015. 2, 6

    work page 2015

  2. [2]

    Parameterized 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. Parameterized approximation schemes for clustering with general norm objectives. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 1377–1399, 2023. 2

    work page 2023

  3. [3]

    Constant-factor FPT approximation for capacitatedk-median

    Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlo- darczyk. Constant-factor FPT approximation for capacitatedk-median. In27th Annual European Symposium on Algorithms, ESA 2019, volume 144, pages 1:1–1:14, 2019. 2, 6

    work page 2019

  4. [4]

    Better guarantees fork-means and euclideank-median by primal-dual algorithms.SIAM Journal on Computing, 49(4), 2020

    Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees fork-means and euclideank-median by primal-dual algorithms.SIAM Journal on Computing, 49(4), 2020. 2, 6

    work page 2020

  5. [5]

    Soroush Alamdari and David B. Shmoys. A bicriteria approximation algorithm for thek-center andk- median problems. InWorkshop on Approximation and Online Algorithms, WAOA 2017, volume 10787, pages 66–75, 2017. 1, 3 21

    work page 2017

  6. [6]

    Centrality of trees for capacitatedk-center.Mathematical Programming, 154(1):29–53, 2015

    Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitatedk-center.Mathematical Programming, 154(1):29–53, 2015. 1, 2, 3

    work page 2015

  7. [7]

    Local search heuristic fork-median and facility location problems

    Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic fork-median and facility location problems. InProceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC 2001, pages 21–29, 2001. 5

    work page 2001

  8. [8]

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

    Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT constant-approximations for capaci- tated clustering to minimize the sum of cluster radii. In39th International Symposium on Computational Geometry, SoCG 2023, volume 258, pages 12:1–12:14, 2023. 6

    work page 2023

  9. [9]

    How to allocate network centers.Journal of Algorithms, 15(3):385–415, 1993

    Judit Barilan, Guy Kortsarz, and David Peleg. How to allocate network centers.Journal of Algorithms, 15(3):385–415, 1993. 2

    work page 1993

  10. [10]

    Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu

    Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022,, pages 462–473,

    work page 2022

  11. [11]

    Jiang, Robert Krauthgamer, and Xuan Wu

    Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. InProceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97, pages 744–753, 2019. 4

    work page 2019

  12. [12]

    Bi-factor approximation algorithms for hard capacitatedk-median problems

    Jaros law Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitatedk-median problems. InProceedings of the 26h Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 722–736, 2014. 2, 6

    work page 2015

  13. [13]

    An improved approximation fork-median and positive correlation in budgeted optimization.ACM Transactions on Algorithms, 13(2):1–31, 2017

    Jaros law Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation fork-median and positive correlation in budgeted optimization.ACM Transactions on Algorithms, 13(2):1–31, 2017. 5

    work page 2017

  14. [14]

    Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh

    Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation fork-median and positive correlation in budgeted optimization.ACM Transactions on Algorithms, 13(2):23:1–23:31, 2017. 2

    work page 2017

  15. [15]

    An approximation algorithm for uniform ca- pacitatedk-median problem with (1 +ϵ)-capacity violation

    Jaros law Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform ca- pacitatedk-median problem with (1 +ϵ)-capacity violation. InInternational Conference on Integer Programming and Combinatorial Optimization, IPCO 2016, volume 9682, pages 262–274, 2016. 2, 6

    work page 2016

  16. [16]

    Constant-factor approximation for ordered k-median

    Jaroslaw Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k-median. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 620–631, 2018. 2

    work page 2018

  17. [17]

    Interpolating betweenk-median andk-center: Approx- imation algorithms for orderedk-median

    Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating betweenk-median andk-center: Approx- imation algorithms for orderedk-median. In45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107, pages 29:1–29:14, 2018. 1, 2, 5, 7

    work page 2018

  18. [18]

    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 Symposium on Theory of Computing, STOC 2019, pages 126–137, 2019. 2

    work page 2019

  19. [19]

    Improved combinatorial algorithms for the facility location and k-median problems

    Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pages 378–388, 1999. 2, 5 22

    work page 1999

  20. [20]

    Moses Charikar, Sudipto Guha, ´Eva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for thek-median problem.Journal of Computer and System Sciences, 65(1):129–149, 2002. 5

    work page 2002

  21. [21]

    Onk-median clustering in high dimensions

    Ke Chen. Onk-median clustering in high dimensions. InProceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pages 1177–1185, 2006. 4

    work page 2006

  22. [22]

    On coresets fork-median andk-means clustering in metric and euclidean spaces and their applications.SIAM Journal on Computing, 39(3):923–947, 2009

    Ke Chen. On coresets fork-median andk-means clustering in metric and euclidean spaces and their applications.SIAM Journal on Computing, 39(3):923–947, 2009. 4

    work page 2009

  23. [23]

    Approximatingk-median with non-uniform capacities

    Julia Chuzhoy and Yuval Rabani. Approximatingk-median with non-uniform capacities. InProceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, volume 5, pages 952– 958, 2005. 2, 6

    work page 2005

  24. [24]

    Improved approx- imations for euclideank-means andk-median, via nested quasi-independent sets

    Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Improved approx- imations for euclideank-means andk-median, via nested quasi-independent sets. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1621–1628, 2022. 2

    work page 2022

  25. [25]

    Near-linear time approximation schemes for clustering in doubling metrics.Journal of the ACM, 68(6):1–34, 2021

    Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics.Journal of the ACM, 68(6):1–34, 2021. 2

    work page 2021

  26. [26]

    A (2+ϵ)-approximation algorithm for metrick-median

    Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson. A (2+ϵ)-approximation algorithm for metrick-median. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 615–624, 2025. 2, 5

    work page 2025

  27. [27]

    An improved local search algorithm fork-median

    Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm fork-median. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 1556–1612, 2022. 5

    work page 2022

  28. [28]

    Tight FPT Ap- proximations fork-Median andk-Means

    Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Ap- proximations fork-Median andk-Means. In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132, pages 42:1–42:14, 2019. 2, 5

    work page 2019

  29. [29]

    On the fixed-parameter tractability of capacitated clustering

    Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132, pages 41–1, 2019. 1, 2, 3, 4, 6

    work page 2019

  30. [30]

    Lp rounding fork-centers with non- uniform hard capacities

    Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. Lp rounding fork-centers with non- uniform hard capacities. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 273–282, 2012. 2

    work page 2012

  31. [31]

    Constant approximation for capacitatedk-median with (1 +ϵ)-capacity violation

    G¨ okalp Demirci and Shi Li. Constant approximation for capacitatedk-median with (1 +ϵ)-capacity violation. In43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, volume 55, pages 73:1–73:14, 2016. 2, 6

    work page 2016

  32. [32]

    Klein, and Claire Mathieu

    David Eisenstat, Philip N. Klein, and Claire Mathieu. Approximatingk-center in planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 617–627, 2014. 2

    work page 2014

  33. [33]

    A tight bound on approximating arbitrary metrics by tree metrics

    Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. InProceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, pages 448–455, 2003. 2

    work page 2003

  34. [34]

    Optimal algorithms for approximate clustering

    Tom´ as Feder and Daniel Greene. Optimal algorithms for approximate clustering. InProceedings of the 21th Annual ACM Symposium on Theory of Computing, STOC 1988, pages 434–444, 1988. 2 23

    work page 1988

  35. [35]

    A ptas fork-means clustering based on weak coresets

    Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A ptas fork-means clustering based on weak coresets. InProceedings of the 23rd Annual Symposium on Computational Geometry, SoCG 2007, pages 11–18, 2007. 2

    work page 2007

  36. [36]

    Turning big data into tiny data: Constant-size coresets fork-means, pca, and projective clustering.SIAM Journal on Computing, 49(3):601–657, 2020

    Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets fork-means, pca, and projective clustering.SIAM Journal on Computing, 49(3):601–657, 2020. 4

    work page 2020

  37. [37]

    A unified framework of FPT approximation algorithms for clustering problems

    Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. A unified framework of FPT approximation algorithms for clustering problems. In31st International Symposium on Algorithms and Computation, ISAAC 2020, volume 181, pages 5:1–5:17, 2020. 6

    work page 2020

  38. [38]

    Local search yields a ptas for k-means in doubling metrics.SIAM Journal on Computing, 48(2):452–480, 2019

    Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour. Local search yields a ptas for k-means in doubling metrics.SIAM Journal on Computing, 48(2):452–480, 2019. 2

    work page 2019

  39. [39]

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

    work page 1985

  40. [40]

    Tight FPT approximation for constrainedk-center andk-supplier

    Dishant Goyal and Ragesh Jaiswal. Tight FPT approximation for constrainedk-center andk-supplier. Theoretical Computer Science, 940:190–208, 2023. 2, 3

    work page 2023

  41. [41]

    Tight FPT approximation for socially fair clustering.Information Processing Letters, 182:106383, 2023

    Dishant Goyal and Ragesh Jaiswal. Tight FPT approximation for socially fair clustering.Information Processing Letters, 182:106383, 2023. 6

    work page 2023

  42. [42]

    Greedy strikes back: Improved facility location algorithms.Journal of Algorithms, 31(1):228–248, 1999

    Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms.Journal of Algorithms, 31(1):228–248, 1999. 2

    work page 1999

  43. [43]

    Simpler Analyses of Local Search Algorithms for Facility Location

    Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility loca- tion.arXiv preprint arXiv:0809.2554, 2008. 6

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  44. [44]

    A best possible heuristic for thek-center problem.Mathematics of Operations Research, 10(2):180–184, 1985

    Dorit S Hochbaum and David B Shmoys. A best possible heuristic for thek-center problem.Mathematics of Operations Research, 10(2):180–184, 1985. 2, 5

    work page 1985

  45. [45]

    A unified approach to approximation algorithms for bottleneck problems.Journal of the ACM, 33(3):533–550, 1986

    Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems.Journal of the ACM, 33(3):533–550, 1986. 2

    work page 1986

  46. [46]

    Coresets for constrained clustering: General assignment constraints and improved size bounds

    Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 4732–4782, 2025. 4

    work page 2025

  47. [47]

    Vazirani

    Kamal Jain and Vijay V. Vazirani. Primal-dual approximation algorithms for metric facility location andk-median problems. In40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pages 2–13, 1999. 2

    work page 1999

  48. [48]

    Approximation algorithms for metric facility location andk-median problems using the primal-dual schema and lagrangian relaxation.Journal of the ACM, 48(2):274–296,

    Kamal Jain and Vijay V Vazirani. Approximation algorithms for metric facility location andk-median problems using the primal-dual schema and lagrangian relaxation.Journal of the ACM, 48(2):274–296,

    work page

  49. [49]

    A local search approximation algorithm fork-means clustering

    Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm fork-means clustering. InProceedings of the 18th Annual Symposium on Computational Geometry, SoCG 2002, pages 10–18, 2002. 6

    work page 2002

  50. [50]

    The capacitatedk-center problem.SIAM Journal on Discrete Mathematics, 13(3):403–418, 2000

    Samir Khuller and Yoram J Sussmann. The capacitatedk-center problem.SIAM Journal on Discrete Mathematics, 13(3):403–418, 2000. 2

    work page 2000

  51. [51]

    A betterk-means++ algorithm via local search

    Silvio Lattanzi and Christian Sohler. A betterk-means++ algorithm via local search. InProceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97, pages 3662–3671,

    work page 2019

  52. [52]

    An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem

    Shanfei Li. An improved approximation algorithm for the hard uniform capacitatedk-median problem. arXiv preprint arXiv:1406.4454, 2014. 2, 6

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  53. [53]

    Approximating capacitatedk-median with (1 +ϵ)kopen facilities

    Shi Li. Approximating capacitatedk-median with (1 +ϵ)kopen facilities. InProceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 786–796, 2016. 2, 6

    work page 2016

  54. [54]

    On uniform capacitatedk-median beyond the natural lp relaxation.ACM Transactions on Algorithms, 13(2):1–18, 2017

    Shi Li. On uniform capacitatedk-median beyond the natural lp relaxation.ACM Transactions on Algorithms, 13(2):1–18, 2017. 2, 6

    work page 2017

  55. [55]

    A fixed-parameter tractable approximation for capacitated k-supplier.Theoretical Computer Science, page 115605, 2025

    Shuilian Liu, Xianrun Chen, and Yicheng Xu. A fixed-parameter tractable approximation for capacitated k-supplier.Theoretical Computer Science, page 115605, 2025. 6

    work page 2025

  56. [56]

    Least squares quantization in pcm.IEEE Transactions on Information Theory, 28(2):129– 137, 1982

    Stuart Lloyd. Least squares quantization in pcm.IEEE Transactions on Information Theory, 28(2):129– 137, 1982. 6

    work page 1982

  57. [57]

    Fixed parameter tractable algorithm and coreset for the orderedk-median problem, master thesis.https://urn.fi/URN:NBN:fi:aalto-202405193486, 2023

    Michal Osadnik. Fixed parameter tractable algorithm and coreset for the orderedk-median problem, master thesis.https://urn.fi/URN:NBN:fi:aalto-202405193486, 2023. 3

    work page 2023

  58. [58]

    A heuristic for thep-center problems in graphs.Discrete Applied Mathematics, 17(3):263– 268, 1987

    J´ an Plesn´ ık. A heuristic for thep-center problems in graphs.Discrete Applied Mathematics, 17(3):263– 268, 1987. 2, 5

    work page 1987

  59. [59]

    A constant FPT approximation algorithm for hard-capacitated k-means

    Yicheng Xu, Rolf H M¨ ohring, Dachuan Xu, Yong Zhang, and Yifei Zou. A constant parameterized approximation for hard-capacitatedk-means.arXiv preprint arXiv:1901.04628, 2019. 6 A Making Distances Polynomially Bounded In this section, we show how to make distances∞or integers in [0,poly(n)], losing only a (1 +ϵ)-factor in the approximation ratio, for any s...

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  60. [60]

    Ifc∈Cis notX-exclusive for any∅⊊X⊆F, saycisinclusive

    Forc∈Cand∅⊊X⊆F, saycisX-exclusive, if the following two conditions hold: (i)∀f 1, f2 ∈X, d(f1,f2) d(c,X) ≤ϵ; (ii)∀f∈F\X, maxf ′ ∈X d(c,f ′) d(c,f) ≤ϵ. Ifc∈Cis notX-exclusive for any∅⊊X⊆F, saycisinclusive. DefineC X to be the set ofX-exclusive clients, andC I as the set of inclusive clients. We first show that, thoseXwith nonemptyC X forms a laminar family...

    work page