A PTAS for k-means clustering based on weak coresets

DOI10.1145/1247069.1247072zbMath1209.68639OpenAlexW2171125141MaRDI QIDQ3602851

Christian Sohler, Morteza Monemizadeh, Dan Feldman

Publication date: 12 February 2009

Published in: Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1247069.1247072

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

A strong coreset algorithm to accelerate OPF as a graph-based machine learning in large-scale problems, An improved primal-dual approximation algorithm for the k-means problem with penalties, Preclustering algorithms for imprecise points, Unnamed Item, Clustering through continuous facility location problems, A quantization framework for smoothed analysis of Euclidean optimization problems, Clustering with faulty centers, Improved PTAS for the constrained \(k\)-means problem, Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space, Faster algorithms for the constrained \(k\)-means problem, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, Approximate Clustering with Same-Cluster Queries, Facility Location in Dynamic Geometric Data Streams, A Streaming Algorithm for k-Means with Approximate Coreset, Core-Sets: Updated Survey, Local Search Yields a PTAS for $k$-Means in Doubling Metrics, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems, Improved Algorithms for Time Decay Streams, Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, An efficient \(K\)-means clustering algorithm for tall data, FPT Approximation for Constrained Metric k-Median/Means, Unnamed Item, Learning big (image) data via coresets for dictionaries, A unified framework for clustering constrained data without locality property, Coresets for Fuzzy K-Means with Applications, Single facility collection depots location problem in the plane, An approximation algorithm for the uniform capacitated \(k\)-means problem, Unnamed Item, Unnamed Item, Probabilistic \(k\)-median clustering in data streams