A Caltech Library Service

A refined approximation for Euclidean k-means

Grandoni, Fabrizio and Ostrovsky, Rafail and Rabani, Yuval and Schulman, Leonard J. and Venkat, Rakesh (2022) A refined approximation for Euclidean k-means. Information Processing Letters, 176 . Art. No. 106251. ISSN 0020-0190. doi:10.1016/j.ipl.2022.106251.

[img] PDF - Published Version
Creative Commons Attribution Non-commercial No Derivatives.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Grandoni, Fabrizio0000-0002-9676-4931
Rabani, Yuval0000-0001-7772-2544
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)200020B_182865/1
Binational Science Foundation (USA-Israel)2015782
Binational Science Foundation (USA-Israel)2018687
Israel Science Foundation956-15
Israel Science Foundation2533-17
Israel Science Foundation3565-21
Subject Keywords:Approximation algorithms; Euclidean k-means; Euclidean facility location; Integrality gaps
Record Number:CaltechAUTHORS:20220204-680165000
Persistent URL:
Official Citation:Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat, A refined approximation for Euclidean k-means, Information Processing Letters, Volume 176, 2022, 106251, ISSN 0020-0190,
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113295
Deposited By: George Porter
Deposited On:07 Feb 2022 15:08
Last Modified:07 Feb 2022 15:08

Repository Staff Only: item control page