k-Means Has Polynomial Smoothed Complexity
From MaRDI portal
Publication:5171190
DOI10.1109/FOCS.2009.14zbMath1292.68187OpenAlexW2170648111MaRDI QIDQ5171190
Bodo Manthey, David Arthur, 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
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Pattern recognition, speech recognition (68T10)
Related Items (7)
An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Fuzzy regularized generalized eigenvalue classifier with a novel membership function ⋮ A Bad Instance for k-Means++ ⋮ Settling the Complexity of Local Max-Cut (Almost) Completely ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ Minimax and Minimax Projection Designs Using Clustering
This page was built for publication: k-Means Has Polynomial Smoothed Complexity
