A refined approximation for Euclidean k-means

Creators: Grandoni, Fabrizio; Ostrovsky, Rafail; Rabani, Yuval; Schulman, Leonard J.; Venkat, Rakesh

Abstract

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

1-s2.0-S0020019022000084-main.pdf

Files (270.6 kB)

Name	Size	Download all
1-s2.0-S0020019022000084-main.pdf md5:c9fcdeb8628be94e3c8fe367f81d8931	270.6 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes