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. https://resolver.caltech.edu/CaltechAUTHORS:20220204-680165000
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution Non-commercial No Derivatives. 270kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220204-680165000
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.
| Item Type: | Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||||||||
| ORCID: |
| ||||||||||||||||||
| 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. | ||||||||||||||||||
| Funders: |
| ||||||||||||||||||
| Subject Keywords: | Approximation algorithms; Euclidean k-means; Euclidean facility location; Integrality gaps | ||||||||||||||||||
| DOI: | 10.1016/j.ipl.2022.106251 | ||||||||||||||||||
| Record Number: | CaltechAUTHORS:20220204-680165000 | ||||||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220204-680165000 | ||||||||||||||||||
| 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, https://doi.org/10.1016/j.ipl.2022.106251. | ||||||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||
| ID Code: | 113295 | ||||||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||||||
| Deposited By: | George Porter | ||||||||||||||||||
| Deposited On: | 07 Feb 2022 15:08 | ||||||||||||||||||
| Last Modified: | 07 Feb 2022 15:08 |
Repository Staff Only: item control page
