The Planar k-Means Problem is NP-Hard

DOI10.1007/978-3-642-00202-1_24zbMath1211.68212OpenAlexW2103718624WikidataQ56449832 ScholiaQ56449832MaRDI QIDQ3605504

Prajakta Nimbhorkar, Meena Mahajan, Kasturi R. Varadarajan

Publication date: 24 February 2009

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_24

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 (45)

Local Versions of Sum-of-Norms Clustering ⋮ A Distance-Preserving Matrix Sketch ⋮ The Ratio-Cut Polytope and K-Means Clustering ⋮ Clustering through continuous facility location problems ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ On strategies to fix degenerate \(k\)-means solutions ⋮ On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications ⋮ A bad instance for \texttt{k-means++} ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ On the complexity of redescription mining ⋮ Dynamic parameters in sequential decision making ⋮ Global optimality in \(k\)-means clustering ⋮ Strategic oscillation for the balanced minimum sum-of-squares clustering problem ⋮ Structured filtering ⋮ Optimising sum-of-squares measures for clustering multisets defined over a metric space ⋮ A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ Parameterized \(k\)-clustering: tractability island ⋮ An improved column generation algorithm for minimum sum-of-squares clustering ⋮ Core-Sets: Updated Survey ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Hardness of \(k\)-anonymous microaggregation ⋮ Improved and simplified inapproximability for \(k\)-means ⋮ An efficient \(K\)-means clustering algorithm for tall data ⋮ EMERGING CLUSTER ANALYSIS OF SCI JOURNALS AND ITS EFFICIENCY ⋮ Boolean autoencoders and hypercube clustering complexity ⋮ Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems ⋮ Temporally consistent tone mapping of images and video using optimal \(K\)-means clustering ⋮ Unnamed Item ⋮ A dual reformulation and solution framework for regularized convex clustering problems ⋮ When do birds of a feather flock together? \(k\)-means, proximity, and conic programming ⋮ Convex programming based spectral clustering ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ A Performance Guarantee for Spectral Clustering ⋮ An approximation algorithm for the spherical \(k\)-means problem with outliers by local search ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum-inspired ant lion-optimized hybrid fuzzy c-means method for fuzzy clustering and image segmentation ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ Scenario reduction revisited: fundamental limits and guarantees

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• A local search approximation algorithm for \(k\)-means clustering
• Clustering large graphs via the singular value decomposition
• NP-hardness of Euclidean sum-of-squares clustering
• How fast is the \(k\)-means method?
• On the Complexity of Some Common Geometric Location Problems
• On Metric Clustering to Minimize the Sum of Radii
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Approximation schemes for clustering problems
• Universality considerations in VLSI circuits
• Planar Formulae and Their Uses
• Least squares quantization in PCM
• The effectiveness of lloyd-type methods for the k-means problem
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: The Planar k-Means Problem is NP-Hard