\(k\)-means requires exponentially many iterations even in the plane

DOI10.1007/s00454-011-9340-1zbMath1218.68088OpenAlexW2950437976WikidataQ56480221 ScholiaQ56480221MaRDI QIDQ540436

Andrea Vattani

Publication date: 3 June 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-011-9340-1

zbMATH Keywords

local searchlower bounds\(k\)-means

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

A refined approximation for Euclidean \(k\)-means ⋮ Fast indefinite multi-point (IMP) clustering ⋮ Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems ⋮ On the minimum of the mean-squared error in 2-means clustering ⋮ Exact algorithms for size constrained 2-clustering in the plane ⋮ Iterative ensemble normalized cuts ⋮ A bad instance for \texttt{k-means++} ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ On the complexity of clustering with relaxed size constraints in fixed dimension ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ A Bad Instance for k-Means++ ⋮ An efficient \(K\)-means clustering algorithm for tall data ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ When do birds of a feather flock together? \(k\)-means, proximity, and conic programming ⋮ Good Clusterings Have Large Volume ⋮ Construction of the similarity matrix for the spectral clustering method: numerical experiments ⋮ On the Complexity of Clustering with Relaxed Size Constraints ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ The seeding algorithm for spherical \(k\)-means clustering with penalties

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• How fast is the \(k\)-means method?
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Smoothed analysis of algorithms
• Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
• Least squares quantization in PCM
• k-Means Has Polynomial Smoothed Complexity
• k-means requires exponentially many iterations even in the plane

This page was built for publication: \(k\)-means requires exponentially many iterations even in the plane