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

DOI10.1016/J.IPL.2014.07.009zbMATH Open1302.68341arXiv1401.3685OpenAlexW2046816920MaRDI QIDQ477594FDOQ477594

Authors: Ragesh Jaiswal, Mehul Kumar, Pulkit Yadav 

Publication date: 9 December 2014

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

Abstract: We give an improved analysis of the simple $D^2$-sampling based PTAS for the $k$-means clustering problem given by Jaiswal, Kumar, and Sen (Algorithmica, 2013). The improvement on the running time is from $Oleft(ndcdot{2}^{ildeO(k^2/epsilon)}ight)$ to $Oleft(ndcdot{2}^{ildeO(k/epsilon)}ight)$.

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

Recommendations

• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Improved PTAS for the constrained \(k\)-means problem
• Adaptive Sampling for k-Means Clustering
• On variants of \(k\)-means clustering

zbMATH Keywords

\(k\)-means clusteringrandomized algorithmsPTAS\(D^2\)-sampling

Mathematics Subject Classification ID

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

Cites Work

• Clustering for metric and nonmetric distance measures
• Linear-time approximation schemes for clustering problems in any dimensions
• Coresets and approximate clustering for Bregman divergences

Cited In (12)

• k-means-g*: accelerating \(k\)-means clustering algorithm utilizing primitive geometric concepts
• A unified framework of FPT approximation algorithms for clustering problems
• Analysis of an innovative sampling strategy based on k-means clustering algorithm for POD and POD-DEIM reduced order models of a 2-D reaction-diffusion system
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• Approximate Clustering with Same-Cluster Queries
• Faster balanced clusterings in high dimension
• Faster algorithms for the constrained \(k\)-means problem
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Improved PTAS for the constrained \(k\)-means problem
• Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes
• Semimetric properties of Sørensen-Dice and Tversky indexes
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems

This page was built for publication: Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems

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