Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

Abstract

This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using $\tilde{O}(n^{4/5})$ space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a $\mathrm{polylog}(n)$ approximation for general graphs using $\mathrm{polylog}(n)$ space in random order streams, respectively. In addition, we give a space lower bound of $\Omega (n^{1-\epsilon })$ for any randomized algorithm estimating the size of a maximum matching up to a $1+O(\epsilon )$ factor for adversarial streams.

References in corpus (3)

• Improved approximation guarantees for weighted matching in the semi-streaming model
• Kernelization via Sampling with Applications to Dynamic Graph Streams
• Tight Bounds for Linear Sketches of Approximate Matchings

Cited by in corpus (12)

• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• A $(2+\epsilon )$-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Testable Bounded Degree Graph Properties Are Random Order Streamable
• On Approximating Functions of the Singular Values in a Stream
• Optimal lower bounds for universal relation, samplers, and finding duplicates
• Densest Subgraph in Dynamic Graph Streams
• Estimating Weighted Matchings in $o(n)$ Space
• Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
• A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
• Metric Sublinear Algorithms via Linear Sampling
• Estimating Graph Parameters from Random Order Streams