Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences

DOI10.1007/978-3-642-10631-6_103zbMath1273.68152OpenAlexW2098375959MaRDI QIDQ3652289

Bodo Manthey, Heiko Röglin

Publication date: 17 December 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_103

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

On smoothed analysis of quicksort and Hoare's find ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ Low-Rank Approximation and Completion of Positive Tensors

This page was built for publication: Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences