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 (24)

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 ⋮ Streaming Euclidean MST to a constant factor ⋮ Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction ⋮ 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

This page was built for publication: Coresets in dynamic geometric data streams