Worst-case and smoothed analysis of k-means clustering with Bregman divergences

DOI10.20382/JOCG.V4I1A5zbMATH Open1404.68197OpenAlexW2166752738MaRDI QIDQ2968098FDOQ2968098

Authors: Bodo Manthey, Heiko Röglin 

Publication date: 9 March 2017

Full work available at URL: https://doi.org/10.20382/jocg.v4i1a5

Recommendations

• Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
• Smoothed analysis of the \(k\)-means method
• Improved smoothed analysis of the \(k\)-means method
• Improved local search algorithms for Bregman \(k\)-means and its variants
• Clustering with Bregman divergences.

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (9)

• Robust Bregman clustering
• Clustering with Bregman divergences.
• Clustering in Hilbert's projective geometry: the case studies of the probability simplex and the elliptope of correlation matrices
• Smoothed analysis of the \(k\)-means method
• On clustering histograms with \(k\)-means by using mixed \(\alpha\)-divergences
• Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
• Improved smoothed analysis of the \(k\)-means method
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Smoothed analysis of local search algorithms

This page was built for publication: Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences

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