The Planar k-Means Problem is NP-Hard

DOI10.1007/978-3-642-00202-1_24zbMATH Open1211.68212OpenAlexW2103718624WikidataQ56449832 ScholiaQ56449832MaRDI QIDQ3605504FDOQ3605504

Authors: Meena Mahajan, Prajakta Nimbhorkar, Kasturi 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

Recommendations

• The planar \(k\)-means problem is NP-hard
• The hardness of approximation of Euclidean \(k\)-means
• NP-completeness of the Planar Separator Problems
• scientific article; zbMATH DE number 26490
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• \(k\)-means requires exponentially many iterations even in the plane
• \(k\)-means requires exponentially many iterations even in the plane
• Approximation algorithms for NP-complete problems on planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard

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)

Cites Work

• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• Planar Formulae and Their Uses
• Clustering large graphs via the singular value decomposition
• Title not available (Why is that?)
• On the Complexity of Some Common Geometric Location Problems
• Universality considerations in VLSI circuits
• Approximation schemes for clustering 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
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• A local search approximation algorithm for \(k\)-means clustering
• How fast is the \(k\)-means method?

Cited In (48)

• A Distance-Preserving Matrix Sketch
• On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications
• Hardness of \(k\)-anonymous microaggregation
• An efficient \(K\)-means clustering algorithm for tall data
• The hardness of approximation of Euclidean \(k\)-means
• Quantum-inspired ant lion-optimized hybrid fuzzy c-means method for fuzzy clustering and image segmentation
• Boolean autoencoders and hypercube clustering complexity
• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• The ratio-cut polytope and K-means clustering
• Strategic oscillation for the balanced minimum sum-of-squares clustering problem
• Local versions of sum-of-norms clustering
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• A bad instance for \texttt{k-means++}
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• The planar \(k\)-means problem is NP-hard
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• On strategies to fix degenerate \(k\)-means solutions
• Temporally consistent tone mapping of images and video using optimal \(K\)-means clustering
• Structured filtering
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• An improved column generation algorithm for minimum sum-of-squares clustering
• Effective Heuristic Techniques for Combined Robust Clustering Problem
• Parameterized \(k\)-clustering: tractability island
• Local search approximation algorithms for the \(k\)-means problem with penalties
• A dual reformulation and solution framework for regularized convex clustering problems
• Convex programming based spectral clustering
• A performance guarantee for spectral clustering
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• Noisy, Greedy and Not so Greedy k-Means++
• Optimality of spectral clustering in the Gaussian mixture model
• Scenario reduction revisited: fundamental limits and guarantees
• Emerging cluster analysis of SCI journals and its efficiency
• Clustering through continuous facility location problems
• On the hardness of energy minimisation for crystal structure prediction
• Global optimality in \(k\)-means clustering
• On the complexity of redescription mining
• Dynamic parameters in sequential decision making
• Data reduction for weighted and outlier-resistant clustering
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Title not available (Why is that?)
• Improved and simplified inapproximability for \(k\)-means
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• Optimising sum-of-squares measures for clustering multisets defined over a metric space
• An approximation algorithm for the spherical \(k\)-means problem with outliers by local search
• Core-sets: updated survey

Uses Software

• k-means++

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

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