# Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 78 references that are in the map.
- First posted on arXiv 21 Nov 2021.

## Builds on (most cited first, 18 of 18)

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [A Fast Approximation Scheme for Low-Dimensional k-Means](https://mlsanity.com/paper/1708.07381/) (2017)
- [Tight FPT Approximations for k-Median and k-Means](https://mlsanity.com/paper/1904.12334/) (2019)
- [On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic](https://mlsanity.com/paper/1812.00901/) (2018)
- [Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)](https://mlsanity.com/paper/1910.11850/) (2019)
- [Hardness of Approximation of Euclidean k-Median](https://mlsanity.com/paper/2011.04221/) (2020)
- [The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into ℓ1](https://mlsanity.com/paper/1305.4581/) (2013)
- [On Approximating Maximum Independent Set of Rectangles](https://mlsanity.com/paper/1608.00271/) (2016)
- [On the Complexity of Closest Pair via Polar-Pair of Point-Sets](https://mlsanity.com/paper/1608.03245/) (2016)
- [Approximating Constraint Satisfaction Problems on High-Dimensional Expanders](https://mlsanity.com/paper/1907.07833/) (2019)
- [A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation](https://mlsanity.com/paper/1810.03792/) (2018)
- [Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture](https://mlsanity.com/paper/2008.07344/) (2020)

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

- [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)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Clustering Categorical Data: Soft Rounding k-modes](https://mlsanity.com/paper/2210.09640/) (2022)

## Abstract (arXiv)

K-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in ℓp-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives in ℓp-metrics. We introduce a new hypothesis called the Johnson Coverage Hypothesis (JCH), which roughly asserts that the well-studied max k-coverage problem on set systems is hard to approximate to a factor greater than 1-1/e, even when the membership graph of the set system is a subgraph of the Johnson graph. We then show that together with generalizations of the embedding techniques introduced by Cohen-Addad and Karthik (FOCS '19), JCH implies hardness of approximation results for k-median and k-means in ℓp-metrics for factors which are close to the ones obtained for general metrics. In particular, assuming JCH we show that it is hard to approximate the k-means objective: bullet Discrete case: To a factor of 3.94 in the ℓ1-metric and to a factor of 1.73 in the ℓ2-metric; this improves upon the previous factor of 1.56 and 1.17 respectively, obtained under UGC. bullet Continuous case: To a factor of 2.10 in the ℓ1-metric and to a factor of 1.36 in the ℓ2-metric; this improves upon the previous factor of 1.07 in the ℓ2-metric obtained under UGC. We also obtain similar improvements under JCH for the k-median objective. Additionally, we prove a weak version of JCH using the work of Dinur et al. (SICOMP '05) on Hypergraph Vertex Cover, and recover all the results stated above of Cohen-Addad and Karthik (FOCS '19) to (nearly) the same inapproximability factors but now under the standard NPneqP assumption (instead of UGC).