Improved and simplified inapproximability for k-means

The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their closest respective center. Awasthi et. al. recently showed that there exists a constant c > 1 such that it is NP-hard to approximate the k-means objective within a factor of c. We establish that the constant c is at least 1.0013.

• Publication year

  2015

• Venue

  Information Processing Letters

• Publication date

  2015-09-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.ipl.2016.11.009arXiv 1509.00916
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A remark on a theorem of

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

  2015cited by this paper
• A unified framework for approximating and clustering data

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

  2009cited 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
• Complexity of approximating bounded variants of optimization problems

  2006influential reference
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005cited by this paper
• On the hardness of approximating minimum vertex cover

  2005cited by this paper
• A local search approximation algorithm for k-means 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
• Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)

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

  1994cited by this paper
• Least squares quantization in PCM

  1982cited by this paper

• Accelerating k-means ++ Algorithm

  2025cites this paper
• A cutting plane algorithm for globally solving low-dimensional k-means problems

  2025influential citation
• Learning Augmented Graph k-Clustering

  2025influential citation
• A (2+ε)-Approximation Algorithm for Metric 𝑘-Median

  2025cites this paper
• Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems

  2025cites this paper
• A cutting plane algorithm for globally solving low dimensional k-means clustering problems

  2024cites this paper
• On connections between k-coloring and Euclidean k-means

  2024cites this paper
• On Approximability of ℓ22 Min-Sum Clustering

  2024cites this paper
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems

  2024influential citation
• Faster Approximation Schemes for (Constrained) k-Means with Outliers

  2024cites this paper
• Local Search k-means++ with Foresight

  2024cites this paper
• Multi-Swap k-Means++

  2023influential citation
• Forty years of color quantization: a modern, algorithmic survey

  2023cites this paper
• Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization

  2023influential citation
• Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets

  2022cites this paper
• Towards optimal lower bounds for k-median and k-means coresets

  2022cites this paper
• Near-Optimal Private and Scalable k-Clustering

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

  2022cites this paper
• Machine Unlearning of Federated Clusters

  2022cites this paper
• Analysis of college students’ canteen consumption by broad learning clustering: A case study in Guangdong Province, China

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

  2022cites this paper
• Tackling Provably Hard Representative Selection via Graph Neural Networks

  2022influential citation
• Polylogarithmic Sketches for Clustering

  2022cites this paper
• New Coresets for Projective Clustering and Applications

  2022influential citation
• Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space

  2021cites this paper
• New Aspects of Beyond Worst-Case Analysis

  2021cites this paper
• On fully dynamic constant-factor approximation algorithms for clustering problems

  2021cites this paper
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space

  2021cites this paper
• Cloud Learning Platform Technology of Online Preschool Education Based on Big Data

  2021cites this paper
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

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

  2021cites this paper
• Learning-Augmented k-means Clustering

  2021influential citation
• Dimensionality Reduction for Wasserstein Barycenter

  2021cites this paper
• A Refined Approximation for Euclidean k-Means

  2021cites this paper
• Differentially-Private Clustering of Easy Instances

  2021cites this paper
• Near-optimal Algorithms for Explainable k-Medians and k-Means

  2021cites this paper
• Differentially Private Algorithms for Clustering with Stability Assumptions

  2021cites this paper
• Computational Methods for Liver Vessel Segmentation in Medical Imaging: A Review

  2021cites this paper
• Achieving anonymity via weak lower bound constraints for k-median and k-means

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

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

  2020cites this paper
• Sets Clustering

  2020cites this paper
• The bi-criteria seeding algorithms for two variants of k-means problem

  2020cites this paper
• An approximation algorithm for the uniform capacitated k-means problem

  2020cites this paper
• Research on Indoor Scene Classification Mechanism Based on Multiple Descriptors Fusion

  2020cites this paper
• The provably good parallel seeding algorithms for the k-means problem with penalties

  2020cites this paper
• A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

  2020influential citation
• Differentially Private Clustering: Tight Approximation Ratios

  2020cites this paper
• Clustering under Perturbation Stability in Near-Linear Time

  2020cites this paper
• On Approximability of Clustering Problems Without Candidate Centers

  2020cites this paper
• k-Means: Outliers-Resistant Clustering+++

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

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

  2020cites this paper
• Real-Time Pattern-Recognition of GPR Images with YOLO v3 Implemented by Tensorflow

  2020cites this paper
• Redistricting Algorithms

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

  2020cites this paper
• A Structural Theorem for Center-Based Clustering in High-Dimensional Euclidean Space

  2019cites this paper
• Inapproximability of Clustering in Lp Metrics

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

  2019cites this paper
• Continuous Facility Location Algorithms for k-Means and k-Median

  2019cites this paper
• A constant parameterized approximation for hard-capacitated k-means

  2019cites this paper
• Analysis of Ward's Method

  2019cites this paper
• The seeding algorithm for k-means problem with penalties

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

  2019cites this paper
• Classification and approximation of geometric location problems (Klassifikation und Approximation von Problemen der Geometrischen Platzierung)

  2019cites this paper
• The seeding algorithms for spherical k-means clustering

  2019cites this paper
• Fair Coresets and Streaming Algorithms for Fair k-means

  2019cites this paper
• A constant FPT approximation algorithm for hard-capacitated k-means

  2019cites this paper
• Tight FPT Approximations for $k$-Median and k-Means

  2019cites this paper
• Approximation algorithm for squared metric facility location problem with nonuniform capacities

  2019cites this paper
• A Streaming Algorithm for k-Means with Approximate Coreset

  2019cites this paper
• Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

  2018cites this paper
• Text Steganography in Statistically Clustered Iris Image

  2018cites this paper
• Algorithms For Clustering Problems: Theoretical Guarantees and Empirical Evaluations

  2018cites this paper
• Image Registration Algorithm Based on Parallax Constraint and Clustering Analysis

  2018cites this paper
• NoCS2: Topic-Based Clustering of Big Data Text Corpus in the Cloud

  2018cites this paper
• Combined Elephant Herding Optimization Algorithm with K-means for Data Clustering

  2018cites this paper
• Information Theoretical Clustering Is Hard to Approximate

  2018influential citation
• On the cost of essentially fair clusterings

  2018cites this paper
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means

  2018cites this paper
• Web Intelligence Data Clustering by Bare Bone Fireworks Algorithm Combined with K-Means

  2018cites this paper
• Query K-means Clustering and the Double Dixie Cup Problem

  2018cites this paper
• Cooperative clustering algorithm based on brain storm optimization and K-means

  2018cites this paper
• Fair Coresets and Streaming Algorithms for Fair k-Means Clustering

  2018cites this paper
• Proposal Draft Beyond Worst-Case Analysis in Combinatorial Optimization

  2018cites this paper
• Automatic liver vessel segmentation using 3D region growing and hybrid active contour model

  2018cites this paper
• Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D

  2017cites this paper
• Approximation Schemes for Clustering with Outliers

  2017cites this paper
• D S ] 1 0 A pr 2 01 7 Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms ∗

  2017cites this paper
• New approach to evaluate a non-grain oriented electrical steel electromagnetic performance using photomicrographic analysis via digital image processing

  2017cites this paper
• Approximate Clustering with Same-Cluster Queries

  2017cites this paper
• Constant approximation for k-median and k-means with outliers via iterative rounding

  2017cites this paper
• An LP-based k-means algorithm for balancing weighted point sets

  2017cites this paper
• Clustering Semi-Random Mixtures of Gaussians

  2017cites this paper
• Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems

  2017cites this paper
• Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis

  2017cites this paper
• Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

  2016cites this paper
• Fast agnostic classification

  2016cites this paper
• k-center Clustering under Perturbation Resilience

  2015cites this paper