A Bad Instance for k-Means++

DOI10.1007/978-3-642-20877-5_34zbMath1331.68290OpenAlexW2141650448MaRDI QIDQ3010415

Tobias Brunsch, Heiko Röglin

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_34

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Uses Software

• k-means++

Cites Work

• Unnamed Item
• \(k\)-means requires exponentially many iterations even in the plane
• NP-hardness of Euclidean sum-of-squares clustering
• Adaptive Sampling for k-Means Clustering
• Least squares quantization in PCM
• k-Means Has Polynomial Smoothed Complexity
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: A Bad Instance for k-Means++