\(k\)-means has polynomial smoothed complexity. (English) Zbl 1292.68187
2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 405-414 (2009).
For the entire collection see [Zbl 1293.00016].
MSC:
| 68W40 | Analysis of algorithms |
| 68T10 | Pattern recognition, speech recognition |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
