k-Means Has Polynomial Smoothed Complexity

DOI10.1109/FOCS.2009.14MaRDI QIDQ5171190zbMATH OpenOpenAlexFDO

Authors David Arthur, Bodo Manthey, Heiko Röglin

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.14

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Pattern recognition, speech recognition (68T10) Analysis of algorithms (68W40)

Cited in

(8)

• Minimax and Minimax Projection Designs Using Clustering
• An LP-based k-means algorithm for balancing weighted point sets
• On smoothed analysis of quicksort and Hoare's find
• A bad instance for k-means++
• Settling the complexity of local max-cut (almost) completely
• Fuzzy regularized generalized eigenvalue classifier with a novel membership function
• k-means requires exponentially many iterations even in the plane
• Online simple knapsack with bounded predictions

This page was built for publication: k-Means Has Polynomial Smoothed Complexity

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