Tight lower bound instances for \(k\)-means++ in two dimensions

DOI10.1016/j.tcs.2016.04.012zbMath1339.68218OpenAlexW2341964534MaRDI QIDQ284583

Ragesh Jaiswal, Anup Bhattacharya, Nir Ailon

Publication date: 18 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.012

zbMATH Keywords

lower bounds\(k\)-means++

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

On the \(k\)-means/median cost function ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Noisy, Greedy and Not so Greedy k-Means++

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• A bad instance for \texttt{k-means++}
• The planar \(k\)-means problem is NP-hard
• \(k\)-means++ under approximation stability
• Analysis of k-Means++ for Separable Data
• Bregman Clustering for Separable Instances
• Adaptive Sampling for k-Means Clustering
• k-means requires exponentially many iterations even in the plane

This page was built for publication: Tight lower bound instances for \(k\)-means++ in two dimensions