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

DOI10.1016/J.TCS.2016.04.012zbMATH Open1339.68218OpenAlexW2341964534MaRDI QIDQ284583FDOQ284583

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)

Cites Work

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

Cited In (5)

• Approximate Clustering with Same-Cluster Queries
• Noisy, Greedy and Not so Greedy k-Means++
• On the \(k\)-means/median cost function
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• Improved and simplified inapproximability for \(k\)-means

Uses Software

• k-means++

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

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