A refined approximation for Euclidean \(k\)-means

DOI10.1016/j.ipl.2022.106251zbMath1485.68268arXiv2107.07358OpenAlexW4210590882WikidataQ114167087 ScholiaQ114167087MaRDI QIDQ2122798

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

Publication date: 7 April 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.07358

zbMATH Keywords

approximation algorithmsintegrality gapsEuclidean \(k\)-meansEuclidean facility location

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved and simplified inapproximability for \(k\)-means
• \(k\)-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• On approximate geometric \(k\)-clustering
• Extensions of Lipschitz mappings into a Hilbert space
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation schemes for clustering problems
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Least squares quantization in PCM
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
• Oblivious dimension reduction for k -means: beyond subspaces and the Johnson-Lindenstrauss lemma
• The effectiveness of lloyd-type methods for the k-means problem

This page was built for publication: A refined approximation for Euclidean \(k\)-means