Improved and simplified inapproximability for k-means

DOI10.1016/J.IPL.2016.11.009MaRDI QIDQ506167zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 31 January 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00916

zbMATH Keywords

\(k\)-meansclusteringcomputational complexityhardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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.

Recommendations

• An improved approximation algorithm for the \(k\)-means problem with penalties
• The hardness of approximation of Euclidean k-means
• A tight lower bound instance for k-means++ in constant dimension
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• \(k\)-means++ under approximation stability
• A refined approximation for Euclidean \(k\)-means
• Tight lower bound instances for k-means++ in two dimensions
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• An improved primal-dual approximation algorithm for the k-means problem with penalties
• A fast approximation scheme for low-dimensional k-means

Cites work

• A local search approximation algorithm for \(k\)-means clustering
• A unified framework for approximating and clustering data
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Complexity of approximating bounded variants of optimization problems
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• On the hardness of approximating minimum vertex cover
• Probability and Computing
• The hardness of approximation of Euclidean k-means
• The Planar k-Means Problem is NP-Hard

Cited in

(32)

• An LP-based k-means algorithm for balancing weighted point sets
• The bi-criteria seeding algorithms for two variants of \(k\)-means problem
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• A refined approximation for Euclidean \(k\)-means
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• The seeding algorithm for k-means problem with penalties
• The seeding algorithms for spherical \(k\)-means clustering
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• The planar \(k\)-means problem is NP-hard
• A streaming algorithm for k-means with approximate coreset
• Approximate Clustering with Same-Cluster Queries
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• The hardness of approximation of Euclidean k-means
• Noisy, Greedy and Not so Greedy k-Means++
• On the cost of essentially fair clusterings
• Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets
• The provably good parallel seeding algorithms for the k‐means problem with penalties
• Improved (In-)Approximability Bounds for d-Scattered Set
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Clustering under perturbation stability in near-linear time
• Exact algorithms and lower bounds for stable instances of Euclidean k-means
• Turning big data into tiny data: coresets for unsupervised learning problems
• Achieving anonymity via weak lower bound constraints for k-median and k-means
• Faster approximation schemes for (constrained) k-means with outliers
• On connections between k-coloring and Euclidean k-means
• A cutting plane algorithm for globally solving low-dimensional k-means problems
• On approximability of _2² min-sum clustering

This page was built for publication: Improved and simplified inapproximability for \(k\)-means

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