Adaptive Sampling for k-Means Clustering

DOI10.1007/978-3-642-03685-9_2zbMath1254.68351OpenAlexW1530581016MaRDI QIDQ3638866

Amit Deshpande, Ankit Aggarwal, Ravindran Kannan

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_2

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Related Items (26)

Tight lower bound instances for \(k\)-means++ in two dimensions ⋮ On the \(k\)-means/median cost function ⋮ A bad instance for \texttt{k-means++} ⋮ One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering ⋮ Approximation Algorithms for Matroid and Knapsack Means Problems ⋮ The provably good parallel seeding algorithms for the k‐means problem with penalties ⋮ Semi-supervised k-means++ ⋮ Unnamed Item ⋮ Approximation schemes for \(k\)-facility location ⋮ Approximate Clustering with Same-Cluster Queries ⋮ KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation ⋮ Core-Sets: Updated Survey ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ The Parallel Seeding Algorithm for k-Means Problem with Penalties ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Graph summarization with quality guarantees ⋮ A Bad Instance for k-Means++ ⋮ A bi-criteria analysis for fuzzy \(C\)-means problem ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ The seeding algorithms for spherical \(k\)-means clustering ⋮ The bi-criteria seeding algorithms for two variants of \(k\)-means problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy ⋮ \(k\)-means++ under approximation stability

This page was built for publication: Adaptive Sampling for k-Means Clustering