Streaming Euclidean MST to a constant factor
From MaRDI portal
Publication:6499221
DOI10.1145/3564246.3585168MaRDI QIDQ6499221
Amit Levi, Erik Waingarten, Vincent Cohen-Addad, Rajesh Jayaram, Xi Chen
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On Sketching Quadratic Forms
- Sublinear time algorithms for metric space problems
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Facility Location in Dynamic Geometric Data Streams
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Exponential separation of quantum and classical one-way communication complexity
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Algorithms for dynamic geometric problems over data streams
- Coresets in dynamic geometric data streams
- A randomized linear-time algorithm to find minimum spanning trees
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
- Efficient Sketches for Earth-Mover Distance, with Applications
- Applications of approximation algorithms to cooperative games
- Parallel algorithms for geometric graph problems
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Sampling in dynamic data streams and applications
- Streaming Algorithms via Precision Sampling
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Euclidean Spanners in High Dimensions
- (1 + ε)-Approximation for Facility Location in Data Streams
- Perfect $L_p$ Sampling in a Data Stream
This page was built for publication: Streaming Euclidean MST to a constant factor
