A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems

DOI10.1007/s00453-013-9833-9zbMath1364.68369OpenAlexW2154200889MaRDI QIDQ486976

Ragesh Jaiswal, Sandeep Sen, Amit Kumar

Publication date: 19 January 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9833-9

zbMATH Keywords

samplingPTAS\(k\)-means clustering\(k\)-median

Mathematics Subject Classification ID

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

Related Items (13)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes ⋮ \(k\)-means genetic algorithms with greedy genetic operators ⋮ Approximate Clustering with Same-Cluster Queries ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ Sampling in space restricted settings ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ A unified framework for clustering constrained data without locality property

Uses Software

• k-means++

Cites Work

• On approximate geometric \(k\)-clustering
• Drag forces and heat transfer coefficients for spherical, cuboidal and ellipsoidal particles in cross flow at sub-critical Reynolds numbers
• Clustering for metric and nonmetric distance measures
• Bregman Clustering for Separable Instances
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• Coresets in dynamic geometric data streams
• On k-Median clustering in high dimensions
• A PTAS for k-means clustering based on weak coresets
• Adaptive Sampling for k-Means Clustering
• Least squares quantization in PCM
• Smaller coresets for k-median and k-means clustering
• k-means requires exponentially many iterations even in the plane
• Smoothed Analysis of the k-Means Method
• A unified framework for approximating and clustering data
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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