On coresets for k-means and k-median clustering

DOI10.1145/1007352.1007400zbMath1192.68904OpenAlexW2045964207MaRDI QIDQ3580976

Soham Mazumdar, Sariel Har-Peled

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of statistics (62P99) Approximation algorithms (68W25)

Related Items (70)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ Dynamic coresets ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ Unnamed Item ⋮ Clustering through continuous facility location problems ⋮ How to get close to the median shape ⋮ Summary Data Structures for Massive Data ⋮ Compressive statistical learning with random feature moments ⋮ Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space ⋮ On some variants of Euclidean \(k\)-supplier ⋮ On the \(k\)-means/median cost function ⋮ Streaming with minimum space: an algorithm for covering by two congruent balls ⋮ Approximating ( k,ℓ )-Median Clustering for Polygonal Curves ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Clustering with faulty centers ⋮ Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance ⋮ The Euclidean k-Supplier Problem ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Some results on approximate 1-median selection in metric spaces ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Unnamed Item ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Facility Location in Dynamic Geometric Data Streams ⋮ An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Core-Sets: Updated Survey ⋮ A Family of Unsupervised Sampling Algorithms ⋮ 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 ⋮ Coresets for the Nearest-Neighbor Rule ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ 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 ⋮ One-dimensional \(k\)-center on uncertain data ⋮ An efficient \(K\)-means clustering algorithm for tall data ⋮ Analysis of incomplete data and an intrinsic-dimension Helly theorem ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ An almost space-optimal streaming algorithm for coresets in fixed dimensions ⋮ Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1] ⋮ Sublinear-time Algorithms ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning big (image) data via coresets for dictionaries ⋮ Efficient approximation algorithms for clustering point-sets ⋮ Data Exploration by Representative Region Selection: Axioms and Convergence ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ On coresets for support vector machines ⋮ Unnamed Item ⋮ Clustering with Internal Connectedness ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ On the Optimization Models for Automatic Grouping of Industrial Products by Homogeneous Production Batches ⋮ Algorithms for k-median Clustering over Distributed Streams ⋮ Coresets for Fuzzy K-Means with Applications ⋮ Single facility collection depots location problem in the plane ⋮ Aggregation error for location models: Survey and analysis ⋮ Sublinear‐time approximation algorithms for clustering via random sampling ⋮ Approximate Range Queries for Clustering ⋮ A linear time algorithm for approximate 2-means clustering ⋮ Unnamed Item ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams

This page was built for publication: On coresets for k-means and k-median clustering