The Planar k-Means Problem is NP-Hard

DOI10.1007/978-3-642-00202-1_24MaRDI QIDQ3605504zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• A local search approximation algorithm for \(k\)-means clustering
• Approximation schemes for clustering problems
• Clustering large graphs via the singular value decomposition
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• How fast is the \(k\)-means method?
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• On Metric Clustering to Minimize the Sum of Radii
• On the Complexity of Some Common Geometric Location Problems
• Planar Formulae and Their Uses
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• Universality considerations in VLSI circuits
• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method

Cited in

(48)

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

Describes a project that uses

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)