Coresets in dynamic geometric data streams

DOI10.1145/1060590.1060622zbMath1192.68360OpenAlexW2049744118MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

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