Smoothed Analysis of the k-Means Method
From MaRDI portal
Publication:5395664
DOI10.1145/2027216.2027217zbMath1281.68224OpenAlexW2154714154MaRDI QIDQ5395664
David Arthur, Bodo Manthey, Heiko Röglin
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2027216.2027217
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10)
Related Items (16)
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ A bad instance for \texttt{k-means++} ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Nonlinear multicriteria clustering based on multiple dissimilarity matrices ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Optimising sum-of-squares measures for clustering multisets defined over a metric space ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
This page was built for publication: Smoothed Analysis of the k-Means Method