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

DOI10.1016/J.TCS.2012.02.028zbMATH Open1341.68307OpenAlexW2176996872MaRDI QIDQ393129FDOQ393129

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)

Cites Work

• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• Probability Inequalities for Sums of Bounded Random Variables
• The effectiveness of lloyd-type methods for the k-means problem
• Clustering to minimize the maximum intercluster distance
• Adaptive Sampling for k-Means Clustering
• \(k\)-means requires exponentially many iterations even in the plane
• The Planar k-Means Problem is NP-Hard
• Smoothed Analysis of the k-Means Method
• The Local Nature of List Colorings for Graphs of High Girth

Cited In (6)

• Clustering stability-based evolutionary K-means
• Tight lower bound instances for \(k\)-means++ in two dimensions
• Approximate Clustering with Same-Cluster Queries
• Noisy, Greedy and Not so Greedy k-Means++
• \(k\)-means++ under approximation stability
• Also for \(k\)-means: more data does not imply better performance

Uses Software

• k-means++

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

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