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

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Browse the full SODA paper archive.