Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with k-median:
TR21-177 | 22nd November 2021
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_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 $\ell_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 ... more >>>

ISSN 1433-8092 | Imprint