Noisy, Greedy and Not so Greedy k-Means++

DOI10.4230/LIPIcs.ESA.2020.18OpenAlexW3082390258MaRDI QIDQ5874485

Heiko Röglin, Melanie Schmidt, Jan Eube, Anup Bhattacharya

Publication date: 7 February 2023

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

zbMATH Keywords

greedyadaptive sampling\(k\)-means\(++\)

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Noisy, Greedy and Not so Greedy k-Means++ ⋮ Improved local search algorithms for Bregman \(k\)-means and its variants

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Tight lower bound instances for \(k\)-means++ in two dimensions
• A bad instance for \texttt{k-means++}
• Improved and simplified inapproximability for \(k\)-means
• A local search approximation algorithm for \(k\)-means clustering
• NP-hardness of Euclidean sum-of-squares clustering
• The Planar k-Means Problem is NP-Hard
• Adaptive Sampling for k-Means Clustering
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Least squares quantization in PCM
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• A unified framework for approximating and clustering data
• Noisy, Greedy and Not so Greedy k-Means++