A refined approximation for Euclidean k-means

Grandoni, F. and Ostrovsky, R. and Venkat, Rakesh and et al, . (2022) A refined approximation for Euclidean k-means. Information Processing Letters, 176. pp. 1-7. ISSN 0020-0190

Text
Information_Processing_Letters.pdf - Published Version
Available under License Creative Commons Attribution.
Download (270kB)

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)

[error in script]

IITH Creators:

IITH Creators	ORCiD
Venkat, Rakesh	UNSPECIFIED

Item Type:

Article

Additional Information:

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

Uncontrolled Keywords:

Approximation algorithms, Euclidean facility location, Euclidean k-means, Integrality gaps

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

25 Jun 2022 11:38

Last Modified:

27 Jun 2022 04:44