k-means requires exponentially many iterations even in the plane

DOI10.1145/1542362.1542419zbMath1380.68204OpenAlexW2132958733MaRDI QIDQ5370732

Andrea Vattani

Publication date: 20 October 2017

Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1542362.1542419

zbMATH Keywords

lower bounds\(k\)-means

Mathematics Subject Classification ID

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

Related Items (10)

Tight lower bound instances for \(k\)-means++ in two dimensions ⋮ A selection process for genetic algorithm using clustering analysis ⋮ The planar \(k\)-means problem is NP-hard ⋮ Optimising sum-of-squares measures for clustering multisets defined over a metric space ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ Faster balanced clusterings in high dimension

This page was built for publication: k-means requires exponentially many iterations even in the plane