Coresets in dynamic geometric data streams

DOI10.1145/1060590.1060622zbMath1192.68360MaRDI QIDQ3581392

Gereon Frahling, Christian Sohler

Publication date: 16 August 2010

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

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W25: Approximation algorithms

Related Items

Unnamed Item, Unnamed Item, Sublinear-time Algorithms, Unnamed Item, On Low-Risk Heavy Hitters and Sparse Recovery Schemes, Unnamed Item, Unnamed Item, Unnamed Item, On streaming algorithms for geometric independent set and clique, A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems, An almost space-optimal streaming algorithm for coresets in fixed dimensions, Dynamic coresets, Small space representations for metric min-sum \(k\)-clustering and their applications, A strong coreset algorithm to accelerate OPF as a graph-based machine learning in large-scale problems, Probabilistic \(k\)-median clustering in data streams, Algorithms for k-median Clustering over Distributed Streams, Streaming Embeddings with Slack, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, Sublinear‐time approximation algorithms for clustering via random sampling, Facility Location in Dynamic Geometric Data Streams, An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions