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

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