alphaFeedback

WorksComputer Science

Uniform Capacitated Clustering with Few Extra Centers

AI contributions
Not recorded for this paper
View details

Abstract

In uniform capacitated (k,z)(k,z)-clustering, we open kk centers and assign every client to a center so that no center serves more than UU clients, minimizing the sum of the zz-th powers of the assignment distances; kk-median and kk-means are the cases z=1z=1 and z=2z=2. We study algorithms that may open k+⌊εk⌋k+\lfloor\varepsilon k\rfloor centers for a fixed ε∈(0,1]\varepsilon\in(0,1] and must respect the capacities exactly. In low dimensions, we give deterministic algorithms that are, except for kk-median in the plane, the first polynomial-time algorithms with (1+ε)k(1+\varepsilon)k centers whose ratio is bounded independently of ε\varepsilon. In Euclidean space of any dimension, with clients of bounded doubling dimension, the ratio is Bz−(Bz−1)ε+δ\mathcal{B}_z-(\mathcal{B}_z-1)\varepsilon+δ for every fixed δ>0δ>0, where Bz<3z\mathcal{B}_z<3^z for z>1z>1; this is 3−2ε+δ3-2\varepsilon+δ for kk-median and 5−4ε+δ5-4\varepsilon+δ for kk-means. In doubling metrics, the ratio is 3z−(3z−1)ε+δ3^z-(3^z-1)\varepsilon+δ when centers may share a location, and a constant otherwise, such as min⁡{7−4ε, 3+2ln⁡(1/ε)}+δ\min\{7-4\varepsilon,\,3+2\ln(1/\varepsilon)\}+δ for kk-median. In general metrics, deleting centers greedily gives ratio 3+2ln⁡(1/ε)+δ3+2\ln(1/\varepsilon)+δ for kk-median when centers may share a location and 7+2ln⁡(1/ε)+δ7+2\ln(1/\varepsilon)+δ otherwise, improving the previous O(ε−2log⁡(1/ε))O(\varepsilon^{-2}\log(1/\varepsilon)). Our main tool is a rescue lemma. Splitting a near-optimal uncapacitated solution gives at most 2k−12k-1 blocks of at most UU clients, and giving a block a private center saves its share of the extra cost of following an optimal solution. Since a center of the optimal solution can be closed once all its blocks are rescued, ⌊εk⌋\lfloor\varepsilon k\rfloor extra centers save almost an ε\varepsilon-fraction of this extra cost instead of an ε/2\varepsilon/2-fraction.

Introduction

Clustering with capacities models settings in which a center can handle only a bounded amount of work: a server hosts a limited number of jobs, a facility serves a limited number of customers, and an electoral district contains a bounded number of voters [31, 36]. In the uniform capacitated (k,z)(k,z)-clustering problem, we are given a multiset PP of nn clients in a metric space, a set FF of locations where centers may be opened, and positive integers kk and UU. A solution opens at most kk centers and assigns every client to an open center so that no center serves more than UU clients. Its cost is the sum, over all clients, of the distance to the assigned center raised to a fixed power z≥1z \ge1. The cases z=1z = 1 and z=2z = 2 are capacitated kk-median and capacitated kk-means.

Without capacities, these problems are well understood in low-dimensional spaces: for every fixed zz, they admit polynomial-time approximation schemes in fixed-dimensional Euclidean spaces and in metrics of bounded doubling dimension [14, 71, 35, 57, 32]. All these algorithms rely on locality. In an optimal solution, every client is served by a closest open center, so a region of the space interacts with the rest of the instance only through a few points near its boundary, and a local change of the solution affects only nearby clients. Capacities destroy this property. A client may have to travel to a far-away center because the nearby centers are full, and an algorithm must keep track of how many clients cross every boundary. As a result, much less is known. Arora, Raghavan and Rao [14] gave a quasi-polynomial-time approximation scheme for capacitated kk-median in the plane that violates the capacities by a factor of 1+ε1 + \varepsilon. Cohen-Addad [31] gave approximation schemes that respect uniform capacities, in quasi-polynomial time for kk-median and kk-means in doubling metrics and in polynomial time for kk-median in the plane. Other approximation schemes for capacitated clustering in Euclidean and doubling metrics run in time exponential in kk [CAL19, DX15, BJK18, BFS24, BGI25].

In general metrics, no constant-factor approximation is known even for capacitated kk-median, and the natural LP relaxation has an unbounded integrality gap even if (2−c)k(2-c)k centers may be opened for a constant c>0c > 0 [74]. A long line of work therefore violates the capacities by a factor of 1+ε1 + \varepsilon or opens (1+ε)k(1 + \varepsilon)k centers (§ 3). With (1+ε)k(1 + \varepsilon)k centers, the best previous ratio for uniform capacitated kk-median was O(ε−2log⁡(1/ε))O(\varepsilon^{-2}\log(1/\varepsilon)) [74, 75]. Lower bounds are known only for the uncapacitated problems [31]: kk-median cannot be approximated better than 1+2/e1 + 2/e in general metrics [68], kk-means is APX-hard in high-dimensional Euclidean space [6], under the unique games conjecture both are hard to approximate within some constant factor in high dimensions even with (1+c)k(1+c)k centers for some c>0c > 0 [23], and both are NP-hard in the plane [85, 83].

We study uniform capacitated (k,z)(k,z)-clustering when the algorithm may open

K:=k+⌊εk⌋K := k + \lfloor\varepsilon k \rfloor

centers for a fixed ε∈(0,1]\varepsilon\in(0,1], while the capacities must be respected exactly. In low dimensions, with 2k2k centers, the problem is easy for soft capacities and in Euclidean space: splitting every cluster of a near-optimal uncapacitated solution into blocks of at most UU clients gives fewer than 2k2k centers and a nearly optimal cost (§ 2.1). The question is how fast the ratio grows as the number of extra centers decreases. In low dimensions, we give deterministic polynomial-time algorithms whose ratios stay bounded as ε→0\varepsilon\to0. Except for kk-median in the plane, where a polynomial-time approximation scheme with kk centers is known [31], these are the first polynomial-time algorithms with (1+ε)k(1 + \varepsilon)k centers whose ratio is bounded independently of ε\varepsilon; before, ratios independent of ε\varepsilon in polynomial time needed a constant factor more centers [16, 65] or a constant factor larger capacities [44 BFRS15]. For soft capacities, our ratio is 3z−(3z−1)ε3^z - (3^z - 1)\varepsilon, and in Euclidean space, 3z3^z improves to a smaller constant, such as 55 for kk-means. So the ratio decreases linearly in ε\varepsilon. to the trivial ratio 1 at ε=1\varepsilon= 1, with twice the slope of the bound for rescuing one block per extra center (§ 2.3). For hard capacities, we convert these solutions. In general metrics, deleting centers greedily gives ratio 3+2ln⁡(1/ε)3 + 2\ln(1/\varepsilon) for kk-median with soft capacities and (2+o(1))zln⁡z(1/ε)(2 + o(1))^{z}\ln^{z}(1/\varepsilon) as ε→0\varepsilon\to0 for every zz; in low dimensions, it also improves our ratios for hard capacities when ε\varepsilon is not small.

Our results

Our first result concerns Euclidean space, where centers may be placed anywhere. The dimension dd may be part of the input; only the clients need to have bounded doubling dimension, which holds for every set of clients in fixed dimension.

Theorem 1.1 (Euclidean space). For all fixed κ≥1\kappa\ge1, z≥1z \ge1, ε∈(0,1]\varepsilon\in(0,1] and δ>0\delta> 0, there is a deterministic algorithm that, given nn clients in Rd\mathbb{R}^{d} of doubling dimension at most κ\kappa and integers kk and UU, outputs at most KK centers in Rd\mathbb{R}^{d}, which are distinct if OPT>0\mathrm{OPT} > 0, and an assignment in which every center serves at most UU clients, with cost at most

(Bz−(Bz−1)ε+δ)⋅OPT,where Bz=min⁡{u+2zv:∣1+t∣z≤u+gt+v∣t∣z for all t∈R},\left(B_{z} - (B_{z} - 1)\varepsilon+ \delta\right)\cdot\mathrm{OPT}, \qquad\text{where } B_{z} = \min\{u + 2^{z}v : |1+t|^{z} \le u + gt + v|t|^{z}\text{ for all }t \in\mathbb{R}\},

the minimum is over (u,g,v)∈R3(u,g,v) \in\mathbb{R}^{3}, and OPT\mathrm{OPT} is the optimal cost with kk centers. The running time is polynomial in the input size, with a degree that depends on κ\kappa, zz, ε\varepsilon and δ\delta, but not on dd.

For kk-median and kk-means, B1=3B_{1} = 3 and B2=5B_{2} = 5, so the ratio is 3−2ε+δ3 - 2\varepsilon+ \delta and 5−4ε+δ5 - 4\varepsilon+ \delta. In § 2.8, we show that Bz<3zB_{z} < 3^{z} for z>1z > 1 (Figure 1(d)), that BzB_{z} is the value of a one-dimensional moment problem, and that it is the best constant for movability with optimal representatives (Theorem 2.7).

Four panels showing approximation ratios for soft and hard capacities in various metrics

Figure 1. Our ratios without the additive δ\delta. (a) Soft capacities and Rd\mathbb{R}^d with centers anywhere. (b) Hard capacities in low dimensions: kk-means in doubling metrics and in Rd\mathbb{R}^d with a finite set FF, and kk-median. Each curve is the smaller of the bound of Theorem 1.3 and the greedy bound of Theorem 1.4 with ρ=1\rho=1; the dots mark where the greedy bound becomes smaller. (c) General metrics (Theorem 1.4): 3+2ln⁡(1/ε)3+2\ln(1/\varepsilon) and 7+2ln⁡(1/ε)7+2\ln(1/\varepsilon) for kk-median, and L2(9,ε)L_2(9,\varepsilon) and L2(49,ε)L_2(49,\varepsilon) for kk-means. (d) The ratios as ε→0\varepsilon\to0 for soft capacities and in Rd\mathbb{R}^d, 3z3^z in doubling metrics and BzB_z in Rd\mathbb{R}^d; the values of BzB_z were computed numerically, the dots mark B1=3B_1=3, B2=5B_2=5, B3≈16.83B_3\approx16.83 and B4≈53.41B_4\approx53.41. Panels (b) to (d) use a logarithmic scale.

Our other results concern a metric space in which the set FF of locations is finite. With soft capacities, several centers may be opened at the same location; with hard capacities, every location hosts at most one center. In the theorems below, OPT\mathrm{OPT} is the optimal cost with kk centers under the same type of capacities.

Theorem 1.2 (Soft capacities). For all fixed κ≥1\kappa\ge1, z≥1z \ge1, ε∈(0,1]\varepsilon\in(0,1] and δ>0\delta> 0, there is a deterministic polynomial-time algorithm that, given an instance in which PP or FF has doubling dimension at most κ\kappa, outputs at most KK centers at locations in FF, each serving at most UU clients, with cost at most (3z−(3z−1)ε+δ)⋅OPT(3^{z} - (3^{z} - 1)\varepsilon+ \delta)\cdot\mathrm{OPT}.

Theorem 1.3 (Hard capacities). For all fixed κ≥1\kappa\ge1, z≥1z \ge1, ε∈(0,1]\varepsilon\in(0,1] and δ>0\delta> 0, there is a deterministic polynomial-time algorithm that, given an instance as in Theorem 1.2, outputs at most KK centers at distinct locations in FF, each serving at most UU clients, with cost at most

((1+2(3z−(3z−1)ε)1/z)z+δ)⋅OPT.\left((1 + 2(3^{z} - (3^{z} - 1)\varepsilon)^{1/z})^{z} + \delta\right)\cdot\mathrm{OPT}.

For instances in Rd\mathbb{R}^{d} with clients of doubling dimension at most κ\kappa and a finite set F⊂RdF \subset\mathbb{R}^{d} of locations, 3z3^{z} can be replaced by BzB_{z}, and for kk-means, the cost is at most (11−8ε+25−4ε+δ)⋅OPT(11 - 8\varepsilon+ 2\sqrt{5 - 4\varepsilon} + \delta)\cdot\mathrm{OPT}.

For fixed zz and δ≤1/2\delta\le1/2, if P∪FP \cup F has doubling dimension at most κ\kappa, the algorithms of Theorems 1.2 and 1.3 run in time (n+∣F∣)κ/(εδ)O(κ/δ)(log⁡Δ)O(1)(n + |F|)^{\kappa/(\varepsilon\delta)^{O(\kappa/\delta)}}(\log\Delta)^{O(1)}, where Δ\Delta is the aspect ratio of P∪FP \cup F; if only one side has, as in Theorem 1.1, the exponent becomes (1/(εδ))1/δO(κ)(1/(\varepsilon\delta))^{1/\delta^{O(\kappa)}} (§ 8).

Our last result holds in every finite metric space and for every z≥1z \ge1. For ρ≥1\rho\ge1 and ε∈(0,1]\varepsilon\in(0,1], let Lz(ρ,ε)≥ρL_z(\rho,\varepsilon) \ge\rho be defined by

∫ρLz(ρ,ε)dy(y1/z+2)z−y=ln⁡1ε,\int_{\rho}^{L_z(\rho,\varepsilon)} \frac{dy}{(y^{1/z} + 2)^z - y} = \ln\frac{1}{\varepsilon},

References

  1. [1]Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1377–1399, 2023.
  2. [2]Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Mathematical Programming, 154(1–2):29–53, 2015.
  3. [3]Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), pages 1:1–1:14, 2019.arxiv.org/abs/1809.05791
  4. [4]Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency (FAccT), pages 504–514, 2021.DOI
  5. [6]Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of Euclidean k-means. In Proceedings of the 31st International Symposium on Computational Geometry (SoCG), pages 754–767, 2015.arxiv.org/abs/1502.03316
  6. [7]Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 15–28, 2009.DOI
  7. [8]Barbara M. Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79–101, 2010.DOI
  8. [9]Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544–562, 2004.DOI
  9. [10]Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. Minkowski-type theorems and least-squares clustering. Algorithmica, 20(1):61–76, 1998.DOI
  10. [11]Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approximation. In Advances in Neural Information Processing Systems 22 (NIPS), pages 10–18, 2009.
  11. [12]Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation for facility location with uniform capacities. In Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 149–162, 2010.DOI
  12. [13]Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4):FOCS17–97–FOCS17–156, 2020.
  13. [14]Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 106–113, 1998.
  14. [15]Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272–306, 2017.
  15. [16]Karen Aardal, Pieter L. van den Berg, Dion Gijswijt, and Shanfei Li. Approximation algorithms for hard capacitated k-facility location problems. European Journal of Operational Research, 242(2):358–368, 2015.arxiv.org/abs/1311.4759
  16. [17]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. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 462–473, 2022.arxiv.org/abs/2209.01901
  17. [19]Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and Euclidean spaces and their applications. Journal of Computer and System Sciences, 142:103506, 2024. Preliminary version in ICALP 2021.
  18. [20]Arindam Banerjee and Joydeep Ghosh. Scalable clustering algorithms with balancing constraints. Data Mining and Knowledge Discovery, 13(3):365–395, 2006.DOI
  19. [21]Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 133–144, 2012.DOI
  20. [22]Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar. Clustering under constraints: Efficient parameterized approximation schemes. arXiv:2504.06980v3, 2025.arxiv.org/abs/2504.06980
  21. [23]Anup Bhattacharya, Dishant Goyal, and Ragesh Jaiswal. Hardness of approximation for Euclidean k-median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 4:1–4:23, 2021.DOI
  22. [24]Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. On sampling based algorithms for k-means. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 13:1–13:17, 2020.DOI
  23. [25]Judit Bar-Ilan, Guy Kortsarz, and David Peleg. How to allocate network centers. Journal of Algorithms, 15(3):385–415, 1993.
  24. [26]Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained $k$-means problem. Theory of Computing Systems, 62(1):93–115, 2018.DOI
  25. [28]Michael Balzer, Thomas Schlömer, and Oliver Deussen. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Transactions on Graphics, 28(3):86:1–86:8, 2009.
  26. [29]Sayan Bandyapadhyay and Kasturi R. Varadarajan. On variants of $k$-means clustering. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG), pages 14:1–14:15, 2016.arxiv.org/abs/1512.02985
  27. [30]Vincent Cohen-Addad. A fast approximation scheme for low-dimensional $k$-means. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 430–440, 2018.
  28. [31]Vincent Cohen-Addad. Approximation schemes for capacitated clustering in doubling metrics. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2241–2259, 2020.
  29. [32]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), 2021. Article 44. Preliminary version in FOCS 2019.
  30. [33]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for $k$-median and $k$-means. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 42:1–42:14, 2019.
  31. [34]Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson. A (2 + ε)-approximation algorithm for metric $k$-median. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.
  32. [35]Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for $k$-means and $k$-median in Euclidean and minor-free metrics. SIAM Journal on Computing, 48(2):644–667, 2019. Preliminary version in FOCS 2016.
  33. [36]Vincent Cohen-Addad, Philip N. Klein, and Neal E. Young. Balanced centroidal power diagrams for redistricting. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 389–396, 2018.
  34. [38]Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In Proceedings of the 31st International Symposium on Computational Geometry (SoCG), pages 329–343, 2015.
  35. [42]Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland. An improved greedy approximation for (metric) k-means. In Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 233–240, 2025.
  36. [44]Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129–149, 2002.DOI
  37. [45]Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 273–282, 2012.arxiv.org/abs/1208.3054
  38. [46]Marek Chrobak, Claire Kenyon, and Neal E. Young. The reverse greedy algorithm for the metric k-median problem. Information Processing Letters, 97:68–72, 2006.
  39. [47]Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 952–958, 2005.
  40. [48]Fabián A. Chudak and David P. Williamson. Improved approximation algorithms for capacitated facility location problems. Mathematical Programming, 102(2):207–222, 2005.
  41. [52]Han Dai, Shi Li, and Sijin Peng. On tight FPT time approximation algorithms for \(k\)-clustering problems. In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP), 2026. Article 72.
  42. [53]Aparna Das and Claire Mathieu. A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 73(1):115–142, 2015.DOI
  43. [54]Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1471–1490, 2015.
  44. [56]Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximation schemes for clustering with outliers. ACM Transactions on Algorithms, 15(2):26:1–26:26, 2019. Preliminary version in SODA 2018.
  45. [57]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. Preliminary version in FOCS 2016.
  46. [59]Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. A unified framework of FPT approximation algorithms for clustering problems. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), pages 5:1–5:17, 2020.DOI
  47. [60]Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. FPT approximation for constrained metric \(k\)-median/means. In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC), pages 14:1–14:19, 2020.arxiv.org/abs/2007.11773
  48. [61]Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 534–543, 2003.DOI
  49. [62]Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. arXiv:0809.2554, 2008.arxiv.org/abs/0809.2554
  50. [63]Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4732–4782, 2025.arxiv.org/abs/2301.08460
  51. [64]S. W. Hess, J. B. Weaver, H. J. Siegfeldt, J. N. Whelan, and P. A. Zitlau. Nonpartisan political redistricting by computer. Operations Research, 13(6):998–1006, 1965.DOI
  52. [65]Lu Han, Dachuan Xu, Donglei Du, and Dongmei Zhang. An approximation algorithm for the uniform capacitated k-means problem. Journal of Combinatorial Optimization, 44(3):1812–1823, 2022.
  53. [66]Piotr Indyk. A small approximately min-wise independent family of hash functions. Journal of Algorithms, 38(1):84–90, 2001.DOI
  54. [68]Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 731–740, 2002.
  55. [69]Aditya Jayaprakash and Mohammad R. Salavatipour. Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 877–893, 2022.
  56. [70]Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146–188, 2000. Preliminary version in SODA 1998.
  57. [71]Stavros G. Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the Euclidean k-median problem. SIAM Journal on Computing, 37(3):757–782, 2007.
  58. [72]Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM Journal on Discrete Mathematics, 13(3):403–418, 2000.
  59. [73]Shanfei Li. An improved approximation algorithm for the hard uniform capacitated k-median problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 325–338, 2014.arxiv.org/abs/1406.4454
  60. [74]Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 696–707, 2015.
  61. [75]Shi Li. Approximating capacitated k-median with (1+ε)k open facilities. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 786–796, 2016.
  62. [76]Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM Journal on Computing, 45(2):530–547, 2016.
  63. [77]Retsef Levi, David B. Shmoys, and Chaitanya Swamy. LP-based approximation algorithms for capacitated facility location. Mathematical Programming, 131(1–2):365–379, 2012.
  64. [78]Jyh-Han Lin and Jeffrey Scott Vitter. Approximation algorithms for geometric median problems. Information Processing Letters, 44(5):245–249, 1992.DOI
  65. [79]Jyh-Han Lin and Jeffrey Scott Vitter. ε-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pages 771–782, 1992.
  66. [81]Mikko I. Malinen and Pasi Fränti. Balanced K-means for clustering. In Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR), pages 32–41, 2014.DOI
  67. [82]Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward. A bi-criteria approximation algorithm for k-means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 14:1–14:20, 2016.arxiv.org/abs/1507.04227
  68. [83]Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is NP-hard. Theoretical Computer Science, 442:13–21, 2012.
  69. [84]Konstantin Makarychev, Aravind Reddy, and Liren Shan. Improved guarantees for k-means++ and k-means++ parallel. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.arxiv.org/abs/2010.14487
  70. [85]Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM Journal on Computing, 13(1):182–196, 1984.DOI
  71. [86]Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 3246–3264, 2021.arxiv.org/abs/2103.02512
  72. [87]Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, 36(2):411–432, 2006.DOI
  73. [88]Martin Pál, Éva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 329–338, 2001.DOI
  74. [89]Lloyd S. Shapley. Complements and substitutes in the optimal assignment problem. Naval Research Logistics Quarterly, 9(1):45–48, 1962.
  75. [90]Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 281–290, 2004.
  76. [91]Dennis Wei. A constant-factor bi-criteria approximation guarantee for k-means++. In Advances in Neural Information Processing Systems 29 (NIPS), pages 604–612, 2016.arxiv.org/abs/1605.04986

Paper details

vlnc:W_4hw9b234
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

Not recorded for this paper · View statement →

Looking for related papers…
Contents