A bad instance for \texttt{k-means++}

DOI10.1016/j.tcs.2012.02.028zbMath1341.68307OpenAlexW2176996872MaRDI QIDQ393129

Tobias Brunsch, Heiko Röglin

Publication date: 16 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.028

zbMATH Keywords

clustering\(k\)-means\texttt{k-means++}

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Related Items (5)

Tight lower bound instances for \(k\)-means++ in two dimensions ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ Clustering stability-based evolutionary K-means ⋮ \(k\)-means++ under approximation stability

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
• Clustering to minimize the maximum intercluster distance
• The Planar k-Means Problem is NP-Hard
• Adaptive Sampling for k-Means Clustering
• Least squares quantization in PCM
• Probability Inequalities for Sums of Bounded Random Variables
• Smoothed Analysis of the k-Means Method
• The effectiveness of lloyd-type methods for the k-means problem
• The Local Nature of List Colorings for Graphs of High Girth

This page was built for publication: A bad instance for \texttt{k-means++}