Streaming Euclidean MST to a constant factor

DOI10.1145/3564246.3585168MaRDI QIDQ6499221zbMATH OpenFDO

Authors Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten

Publication date 8 May 2024

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

zbMATH Keywords

sublinear and near linear time algorithmstheory of computation \(\rightarrow\) streaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• (1 + )-approximation for facility location in data streams
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A randomized linear-time algorithm to find minimum spanning trees
• Algorithms for dynamic geometric problems over data streams
• Applications of approximation algorithms to cooperative games
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Coresets in dynamic geometric data streams
• Efficient Sketches for Earth-Mover Distance, with Applications
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Euclidean spanners in high dimensions
• Exponential separation of quantum and classical one-way communication complexity
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Facility Location in Dynamic Geometric Data Streams
• scientific article; zbMATH DE number 5764809 (Why is no real title available?)
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• MST in \(O(1)\) rounds of congested clique
• On sketching quadratic forms
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Parallel algorithms for geometric graph problems
• Perfect \(L_p\) sampling in a data stream
• Sampling in dynamic data streams and applications
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Streaming algorithms via precision sampling
• Sublinear estimation of weighted matchings in dynamic data streams
• Sublinear time algorithms for metric space problems
• The streaming complexity of cycle counting, sorting by reversals, and other problems

Cited in

(5)

• Fully-scalable MPC algorithms for clustering in high dimension
• Moderate dimension reduction for k-center clustering
• Streaming algorithms for geometric Steiner forest
• Range counting oracles for geometric problems
• Streaming diameter of high-dimensional points

This page was built for publication: Streaming Euclidean MST to a constant factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499221)