On Approximability of Clustering Problems Without Candidate Centers

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

The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a conti…