On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Abstract
The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a continuous setting, namely where the centers can be located anywhere in the metric space. For example, the popular Lloyd's heuristic locates a center at the mean of each cluster.
Despite persistent efforts on understanding the approximability of k-means, and other classic clustering problems such as k-median and k-minsum, our knowledge of the hardness of approximation factors of these problems remains quite poor. In this paper, we significantly improve upon the hardness of approximation factors known in the literature for these objectives. We show that if the input lies in a general metric space, it is NP-hard to approximate:
• Continuous k-median to a factor of 2o(1); this improves upon the previous inapproximability factor of 1.36 shown by Guha and Khuller (J. Algorithms '99).
• Continuous k-means to a factor of 4o(1); this improves upon the previous inapproximability factor of 2.10 shown by Guha and Khuller (J. Algorithms '99).
• k-minsum to a factor of 1.415; this improves upon the APX-hardness shown by Guruswami and Indyk (SODA '03).
Our results shed new and perhaps counter-intuitive light on the differences between clustering problems in the continuous setting versus the discrete setting (where the candidate centers are given as part of the input).
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
14 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median cites Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets
- Towards optimal lower bounds for k-median and k-means coresets cites Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets
- Multi-Swap k-Means++ cites Towards optimal lower bounds for k-median and k-means coresets
- Multi-Swap k-Means++ cites Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets
Cited by top-tier papers14
- Better Algorithms for Individually Fair k-ClusteringMaryam Negahbani, Deeparnab ChakrabartyNeurIPS 2021 · 55 citations
- Towards optimal lower bounds for k-median and k-means coresetsVincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris SchwiegelshohnSTOC 2022 · 20 citations
- Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-MedianVincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris SchwiegelshohnSODA 2023 · 16 citations
- Improved approximations for Euclidean k-means and k-median, via nested quasi-independent setsVincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam NarayananSTOC 2022 · 15 citations
- Multi-Swap k-Means++Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos ParotsidisNeurIPS 2023 · 12 citations
Builds on1
Related papers
- An Improved Greedy Approximation for (Metric) k-MeansMoses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni et al.FOCS 2025 · 2 citations
- Parameterized Approximation Algorithms for K-center Clustering and VariantsSayan Bandyapadhyay, Zachary Friggstad, Ramin MousaviAAAI 2022 · 3 citations
- Differentially Private Clustering via Maximum CoverageMatthew Jones, Huy L. Nguyen, Thy Dinh NguyenAAAI 2021 · 28 citations
- Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metricsVincent Cohen-Addad, Karthik C. S., Euiwoong LeeSODA 2022 · 8 citations
- Inapproximability of Maximum Diameter Clustering for Few ClustersHenry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki et al.SODA 2025
