Smoothed Analysis of the k-Means Method

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

zbMATH Keywords

data clusteringsmoothed analysis\(k\)-means method

Mathematics Subject Classification ID

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