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

DOI10.1016/J.IPL.2014.07.009MaRDI QIDQ477594zbMATH OpenOpenAlexFDO

Authors Ragesh Jaiswal, Mehul Kumar, 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

\(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)

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)$.

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

Cites work

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

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
• Faster balanced clusterings in high dimension
• Faster algorithms for the constrained k-means problem
• Approximate Clustering with Same-Cluster Queries
• 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)