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

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

Authors: Anup Bhattacharya, Ragesh Jaiswal, 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

Recommendations

• A tight lower bound instance for \(k\)-means++ in constant dimension
• A bad instance for \texttt{k-means++}
• A bad instance for \(k\)-means++
• Analysis of \(k\)-means++ for separable data
• \(k\)-means++ under approximation stability

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?)
• \(k\)-means++ under approximation stability
• Analysis of \(k\)-means++ for separable data
• Bregman clustering for separable instances
• Title not available (Why is that?)
• 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 (7)

• k-means++ under approximation stability
• Approximate Clustering with Same-Cluster Queries
• A bad instance for \(k\)-means++
• 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)