The planar \(k\)-means problem is NP-hard
From MaRDI portal
Publication:441888
DOI10.1016/j.tcs.2010.05.034zbMath1260.68158OpenAlexW2160039585MaRDI QIDQ441888
Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.034
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (41)
Community detection using local neighborhood in complex networks ⋮ Tight lower bound instances for \(k\)-means++ in two dimensions ⋮ Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ Iterative algorithm for discrete structure recovery ⋮ Exact algorithms for size constrained 2-clustering in the plane ⋮ Preclustering algorithms for imprecise points ⋮ Unsupervised anomaly detection in multivariate time series with online evolving spiking neural networks ⋮ \(k\)-means clustering of extremes ⋮ Energy efficiency optimization for multiple chargers in wireless rechargeable sensor networks ⋮ Discrete facility location in machine learning ⋮ One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Semi-supervised k-means++ ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Efficient, certifiably optimal clustering with applications to latent variable graphical models ⋮ Semi-supervised \(k\)-means clustering via DC programming approach ⋮ How to find a good explanation for clustering? ⋮ Quantizing Rare Random Maps: Application to Flooding Visualization ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ Mixed-integer programming techniques for the minimum sum-of-squares clustering problem ⋮ On the complexity of clustering with relaxed size constraints in fixed dimension ⋮ Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters ⋮ Qualitative properties of the minimum sum-of-squares clustering problem ⋮ Exact Linear-Time Algorithm for Parameterized K-Means Problem with Optimized Number of Clusters in the 1D Case ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Helly-Type Theorems in Property Testing ⋮ Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018 ⋮ Sparse convex hull coverage ⋮ Initializing \(k\)-means clustering by bootstrap and data depth ⋮ Unnamed Item ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Fair redistricting is hard ⋮ Local search approximation algorithms for the sum of squares facility location problems ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension ⋮ Good Clusterings Have Large Volume ⋮ On the Complexity of Clustering with Relaxed Size Constraints ⋮ K-means clustering via a nonconvex optimization approach
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- 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
- k-means requires exponentially many iterations even in the plane
- 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
