Streaming Euclidean MST to a constant factor

DOI10.1145/3564246.3585168MaRDI QIDQ6499221FDOQ6499221

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

Publication date: 8 May 2024

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)