Improved and simplified inapproximability for \(k\)-means

DOI10.1016/j.ipl.2016.11.009zbMath1400.68250arXiv1509.00916OpenAlexW2964283450MaRDI QIDQ506167

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

computational complexityclusteringhardness of approximation\(k\)-means

Mathematics Subject Classification ID

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

Related Items

A refined approximation for Euclidean \(k\)-means ⋮ The provably good parallel seeding algorithms for the k‐means problem with penalties ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Approximate Clustering with Same-Cluster Queries ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ On the cost of essentially fair clusterings ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Unnamed Item ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ 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

Cites Work

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