Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2022 | Published
Journal Article Open

A refined approximation for Euclidean k-means


In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least (16+5√)/15 > 1.2157.

Additional Information

© 2022 The Author(s). Published by Elsevier B.V. Under a Creative Commons license - Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Received 15 July 2021, Accepted 23 January 2022, Available online 2 February 2022, Version of Record 3 February 2022. Work supported in part by the NSF grants 1909972 and CNS-2001096, the SNF excellence grant 200020B_182865/1, the BSF grants 2015782 and 2018687, and the ISF grants 956-15, 2533-17, and 3565-21. The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Attached Files

Published - 1-s2.0-S0020019022000084-main.pdf


Files (270.6 kB)
Name Size Download all
270.6 kB Preview Download

Additional details

August 22, 2023
October 23, 2023