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

DOI10.4230/LIPICS.ESA.2020.18MaRDI QIDQ5874485zbMATH OpenOpenAlexFDO

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

Publication date 7 February 2023

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

zbMATH Keywords

\(k\)-means\(++\)adaptive samplinggreedy

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A bad instance for \texttt{k-means++}
• A local search approximation algorithm for \(k\)-means clustering
• A unified framework for approximating and clustering data
• Adaptive Sampling for k-Means Clustering
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• Improved and simplified inapproximability for \(k\)-means
• Least squares quantization in PCM
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Noisy, Greedy and Not so Greedy k-Means++
• NP-hardness of Euclidean sum-of-squares clustering
• The hardness of approximation of Euclidean k-means
• The Planar k-Means Problem is NP-Hard
• Tight lower bound instances for k-means++ in two dimensions

Cited in

(3)

• Improved local search algorithms for Bregman k-means and its variants
• Noisy, Greedy and Not so Greedy k-Means++
• Also for \(k\)-means: more data does not imply better performance

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Noisy, Greedy and Not so Greedy k-Means++

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874485)