Header menu link for other important links
X
A refined approximation for Euclidean k-means
F. Grandoni, R. Ostrovsky, Y. Rabani, L.J. Schulman,
Published in Elsevier B.V.
2022
Volume: 176
   
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 [Formula presented]. © 2022 The Author(s)
About the journal
JournalData powered by TypesetInformation Processing Letters
PublisherData powered by TypesetElsevier B.V.
ISSN00200190