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

DOI10.1016/J.TCS.2016.04.012MaRDI QIDQ284583zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• A bad instance for \texttt{k-means++}
• Adaptive Sampling for k-Means Clustering
• Analysis of \(k\)-means++ for separable data
• Bregman clustering for separable instances
• The planar \(k\)-means problem is NP-hard
• \(k\)-means requires exponentially many iterations even in the plane
• \(k\)-means++ under approximation stability

Cited in

(10)

• On the \(k\)-means/median cost function
• Noisy, Greedy and Not so Greedy k-Means++
• A bad instance for \texttt{k-means++}
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• A tight lower bound instance for \(k\)-means++ in constant dimension
• k-means++ under approximation stability
• A bad instance for \(k\)-means++
• \(k\)-means++ under approximation stability
• Improved and simplified inapproximability for \(k\)-means
• Approximate Clustering with Same-Cluster Queries

Describes a project that uses

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)