Ahmadian, SaraNorouzi-Fard, AshkanSvensson, OlaWard, Justin2020-09-262020-09-262020-09-262020-01-0110.1137/18M1171321https://infoscience.epfl.ch/handle/20.500.14299/171946WOS:000568207500004Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+epsilon, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard linear programming (LP) relaxation. Our techniques are quite general, and we also show improved guarantees for k-median in Euclidean metrics and for a generalization of k-means in which the underlying metric is not required to be Euclidean.Computer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicsk-meansapproximation algorithmprimal-dualk-medianlp-based algorithmclusteringfacility locationapproximation algorithmstext::journal::journal article::research article