# On Approximability of Clustering Problems Without Candidate Centers

arXiv: https://arxiv.org/abs/2010.00087 · HTML: https://mlsanity.com/paper/2010.00087/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

## Built on by (most cited first, 13 of 13)

- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [Global k-means++: an effective relaxation of the global k-means clustering algorithm](https://mlsanity.com/paper/2211.12271/) (2022)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Learning Augmented Graph k-Clustering](https://mlsanity.com/paper/2506.13533/) (2025)

## Abstract (arXiv)

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: bullet Continuous k-median to a factor of 2-o(1); this improves upon the previous inapproximability factor of 1.36 shown by Guha and Khuller (J. Algorithms '99). bullet Continuous k-means to a factor of 4- o(1); this improves upon the previous inapproximability factor of 2.10 shown by Guha and Khuller (J. Algorithms '99). bullet 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).