2021/11/21 by Vincent Cohen-Addad, C. S. Karthik, Cohen-Addad, Vincent +4 · 1 citation
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Artificial intelligence #Automated Road and Building Extraction #Cluster analysis #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Embedding #FOS: Computer and information sciences #Facility Location and Emergency Management #Factor (programming language) #Graph #Machine Learning (cs.LG) #Mathematics #Metric (unit) #Optimization and Search Problems #Set (abstract data type) #Statistics #cs.CC #cs.CG #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.2111.10912
published in arXiv (Cornell University) (Cornell University) · Abstract in metadata shortened to meet arxiv requirements
arxiv created 2021/11/21 · openalex publication_date 2021/11/21 · arxiv updated 2021/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
K-median and k-means are the two most popular objectives for clustering\nalgorithms. Despite intensive effort, a good understanding of the\napproximability of these objectives, particularly in \ℓp-metrics, remains\na major open problem. In this paper, we significantly improve upon the hardness\nof approximation factors known in literature for these objectives in\n\ℓp-metrics.\n We introduce a new hypothesis called the Johnson Coverage Hypothesis (JCH),\nwhich roughly asserts that the well-studied max k-coverage problem on set\nsystems is hard to approximate to a factor greater than 1-1/e, even when the\nmembership graph of the set system is a subgraph of the Johnson graph. We then\nshow that together with generalizations of the embedding techniques introduced\nby Cohen-Addad and Karthik (FOCS '19), JCH implies hardness of approximation\nresults for k-median and k-means in \ℓp-metrics for factors which are\nclose to the ones obtained for general metrics. In particular, assuming JCH we\nshow that it is hard to approximate the k-means objective:\n bullet Discrete case: To a factor of 3.94 in the \ℓ1-metric and to a\nfactor of 1.73 in the \ℓ2-metric; this improves upon the previous factor\nof 1.56 and 1.17 respectively, obtained under UGC.\n bullet Continuous case: To a factor of 2.10 in the \ℓ1-metric and to\na factor of 1.36 in the \ℓ2-metric; this improves upon the previous factor\nof 1.07 in the \ℓ2-metric obtained under UGC.\n We also obtain similar improvements under JCH for the k-median objective.\nAdditionally, we prove a weak version of JCH using the work of Dinur et al.\n(SICOMP '05) on Hypergraph Vertex Cover, and recover all the results stated\nabove of Cohen-Addad and Karthik (FOCS '19) to (nearly) the same\ninapproximability factors but now under the standard NP\≠P assumption\n(instead of UGC).\n