A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++

This paper studies the $k$-means++ algorithm for clustering as well as the class of $D^\ell$ sampling algorithms to which $k$-means++ belongs. It is shown that for any constant factor $\beta > 1$, selecting $\beta k$ cluster centers by $D^\ell$ sampling yields a constant-factor approximation to the optimal clustering with $k$ centers, in expectation and without conditions on the dataset. This result extends the previously known $O(\log k)$ guarantee for the case $\beta = 1$ to the constant-factor bi-criteria regime. It also improves upon an existing constant-factor bi-criteria result that holds only with constant probability.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-05-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1605.04986
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Local Search Yields a PTAS for k-Means in Doubling Metrics

  2016cited by this paper
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

  2016cited by this paper
• The Hardness of Approximation of Euclidean k-Means

  2015cited by this paper
• A Bi-Criteria Approximation Algorithm for k-Means

  2015influential reference
• On Variants of k-means Clustering

  2015cited by this paper
• A Tight Lower Bound Instance for k-means++ in Constant Dimension

  2014cited by this paper
• A Simple D2-Sampling Based PTAS for k-Means and Other Clustering Problems

  2012cited by this paper
• A bad instance for k-means++

  2011cited by this paper
• Linear-time approximation schemes for clustering problems in any dimensions

  2010cited by this paper
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

  2009cited by this paper
• Adaptive Sampling for k-Means Clustering

  2009influential reference
• Streaming k-means approximation

  2009cited by this paper
• The Planar k-means Problem is NP-hard I

  2009cited by this paper
• Data clustering: 50 years beyond K-means

  2008cited by this paper
• NP-hardness of Euclidean sum-of-squares clustering

  2008cited by this paper
• The hardness of k-means clustering

  2008cited by this paper
• k-means++: the advantages of careful seeding

  2007influential reference
• A PTAS for k-means clustering based on weak coresets

  2007cited by this paper
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  2006cited by this paper
• On coresets for k-means and k-median clustering

  2004cited by this paper
• Local Search Heuristics for k-Median and Facility Location Problems

  2004cited by this paper
• Clustering Data Streams: Theory and Practice

  2003cited by this paper
• Approximation schemes for clustering problems

  2003cited by this paper
• Approximate clustering via core-sets

  2002cited by this paper
• A new greedy approach for facility location problems

  2002cited by this paper
• A local search approximation algorithm for k-means clustering

  2002cited by this paper
• Optimal Time Bounds for Approximate Clustering

  2002cited by this paper
• Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

  2001cited by this paper
• A constant-factor approximation algorithm for the k-median problem (extended abstract)

  1999cited by this paper
• On Approximate Geometric K-clustering

  1999cited by this paper
• Application of weighted Voronoi diagrams and randomization to variance-based k-clustering

  1994cited by this paper
• Least squares quantization in PCM

  1982influential reference

• Improved Algorithms for Clustering with Noisy Distance Oracles

  2026cites this paper
• Accelerating k-means ++ Algorithm

  2025cites this paper
• Toward Understanding the Improved Robustness to Initialization in Distributed Clustering

  2025cites this paper
• Low-Distortion Clustering with Ordinal and Limited Cardinal Information

  2024cites this paper
• Bi-Criteria Metric Distortion

  2024influential citation
• Local Search k-means++ with Foresight

  2024cites this paper
• Fully Scalable MPC Algorithms for Clustering in High Dimension

  2023cites this paper
• Linear Time Algorithms for k-means with Multi-Swap Local Search

  2023cites this paper
• Experimental Evaluation of Fully Dynamic k-Means via Coresets

  2023cites this paper
• An Analysis of $D^\alpha$ seeding for $k$-means

  2023cites this paper
• Noisy k-means++ Revisited

  2023cites this paper
• One-Pass Additive-Error Subset Selection for $$\ell _{p}$$ ℓ p Subspace Approximation and (k, p)-Clustering

  2023influential citation
• An Empirical Evaluation of k-Means Coresets

  2022cites this paper
• A Faster k-means++ Algorithm

  2022cites this paper
• k-Means-MIND: comparing seeds without repeated k-means runs

  2022cites this paper
• A Nearly Tight Analysis of Greedy k-means++

  2022cites this paper
• Distributed k-Means with Outliers in General Metrics

  2022cites this paper
• Adaptive Methods for Aggregated Domain Generalization

  2021cites this paper
• Balanced Districting on Grid Graphs with Provable Compactness and Contiguity

  2021cites this paper
• Uniform and Non-uniform Sampling Methods for Sub-linear Time k-means Clustering

  2021cites this paper
• A local search algorithm for k-means with outliers

  2021cites this paper
• APPROXIMATION ALGORITHM FOR SPHERICAL k -MEANS PROBLEM WITH PENALTY

  2021cites this paper
• An approximation algorithm for the spherical k-means problem with outliers by local search

  2021cites this paper
• Explainable k-means: don’t be greedy, plant bigger trees!

  2021cites this paper
• Label consistency in overfitted generalized $k$-means

  2021cites this paper
• K-means++: Few More Steps Yield Constant Approximation

  2020influential citation
• The bi-criteria seeding algorithms for two variants of k-means problem

  2020influential citation
• The approximation algorithm based on seeding method for functional $ k $-means problem†

  2020cites this paper
• Hardness of Approximation of Euclidean k-Median

  2020cites this paper
• A survey on theory and algorithms for bm$k$-means problems

  2020cites this paper
• A Bi-criteria Analysis for Fuzzy C-means Problem

  2020cites this paper
• Improved Guarantees for k-means++ and k-means++ Parallel

  2020influential citation
• Feature-Aware Uniform Tessellations on Video Manifold for Content-Sensitive Supervoxels

  2020influential citation
• Development of a Decision Support System for Urban Planning by Using K-means ++ Algorithm

  2020cites this paper
• Simple and sharp analysis of k-means||

  2020cites this paper
• Greedy Sampling for Approximate Clustering in the Presence of Outliers

  2019cites this paper
• Noisy, Greedy and Not So Greedy k-means++

  2019cites this paper
• Improved Algorithms for Clustering with Outliers

  2019cites this paper
• Fast Computation of Content-Sensitive Superpixels and Supervoxels Using Q-Distances

  2019cites this paper
• Distributed Clustering in General Metrics via Coresets

  2019cites this paper
• Accurate MapReduce Algorithms for $k$-median and $k$-means in General Metric Spaces

  2019cites this paper
• Content-Sensitive Supervoxels via Uniform Tessellations on Video Manifolds

  2018influential citation
• Approximate Clustering

  2018cites this paper
• Self-Adaptive k-Means Based on a Covering Algorithm

  2018cites this paper
• Content-Sensitive Supervoxels via Uniform Tessellations on Video Manifolds ( Supplemental Material )

  2018cites this paper
• On the k-Means/Median Cost Function

  2017cites this paper
• Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS

  2017cites this paper
• Discrete-Continuous Splitting for Weakly Supervised Learning

  2017cites this paper
• Hybrid Approach for Data Classification in E-Health Cloud

  2017cites this paper
• Clustering over Multi-Objective Samples: The one2all Sample

  2017cites this paper
• Greedy bi-criteria approximations for k-medians and k-means

  2016influential citation