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

DOI10.4230/LIPICS.ESA.2020.18OpenAlexW3082390258MaRDI QIDQ5874485FDOQ5874485

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

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• Tight lower bound instances for \(k\)-means++ in two dimensions
• Adaptive Sampling for k-Means Clustering
• A bad instance for \texttt{k-means++}
• The Planar k-Means Problem is NP-Hard
• The hardness of approximation of Euclidean \(k\)-means
• A local search approximation algorithm for \(k\)-means clustering
• A unified framework for approximating and clustering data
• Improved and simplified inapproximability for \(k\)-means
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Noisy, Greedy and Not so Greedy k-Means++

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

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)