Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > K-MEDIAN:
Reports tagged with k-median:
TR21-177 | 22nd November 2021
#### 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 >>>