On sampling based algorithms for k-means

DOI10.4230/LIPICS.FSTTCS.2020.13MaRDI QIDQ6839895zbMATH OpenFDO

Authors Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, Amit Kumar

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.13

zbMATH Keywords

\(k\)-meanslow rank approximation

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A local search approximation algorithm for \(k\)-means clustering
• A PTAS for ℓ_p-Low Rank Approximation
• A PTAS for k-means clustering based on weak coresets
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• A unified framework for clustering constrained data without locality property
• Adaptive Sampling for k-Means Clustering
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximate Clustering with Same-Cluster Queries
• Approximation schemes for clustering with outliers
• Better guarantees for k-means and euclidean k-median by primal-dual algorithms
• BICO: BIRCH meets coresets for \(k\)-means clustering
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Fair coresets and streaming algorithms for fair \(k\)-means
• Faster algorithms for the constrained k-means problem
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• Improved analysis of D^2-sampling based PTAS for k-means and other clustering problems
• Inapproximability of clustering in Lp metrics
• Linear-time approximation schemes for clustering problems in any dimensions
• 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
• On coresets for k-means and k-median clustering
• On the local structure of stable clustering instances
• Random sampling with a reservoir
• Semi-supervised algorithms for approximately optimal and accurate clustering
• Stability yields a PTAS for k-median and k-means clustering
• Streaming k-means on well-clusterable data
• The geometry of graphs and some of its algorithmic applications
• The hardness of approximation of Euclidean k-means
• The planar \(k\)-means problem is NP-hard
• Training Gaussian mixture models at scale via coresets

Cited in

(4)

• Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
• Clustering what matters in constrained settings: improved outlier to outlier-free reductions
• Faster approximation schemes for (constrained) k-means with outliers
• Robust-sorting and applications to Ulam-median

This page was built for publication: On sampling based algorithms for \(k\)-means

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