Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems

DOI10.1016/j.ipl.2014.07.009zbMath1302.68341arXiv1401.3685OpenAlexW2046816920MaRDI QIDQ477594

Mehul Kumar, Ragesh Jaiswal, Pulkit Yadav

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.3685

zbMATH Keywords

randomized algorithmsPTAS\(k\)-means clustering\(D^2\)-sampling

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering, Improved PTAS for the constrained \(k\)-means problem, k-means-g*: accelerating \(k\)-means clustering algorithm utilizing primitive geometric concepts, Faster algorithms for the constrained \(k\)-means problem, Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes, Approximate Clustering with Same-Cluster Queries, A unified framework of FPT approximation algorithms for clustering problems, Faster balanced clusterings in high dimension, Semimetric Properties of Sørensen-Dice and Tversky Indexes

Cites Work

• Unnamed Item
• Clustering for metric and nonmetric distance measures
• Linear-time approximation schemes for clustering problems in any dimensions