Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

2015/05/08 by Marc Bury, Chris Schwiegelshohn, Bury, Marc +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Privacy-Preserving Technologies in Data

paper · doi:10.48550/arxiv.1505.02019

openalex publication_date 2015/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(n^4/5) space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a polylog(n) approximation for general graphs using polylog(n) space in random order streams, respectively. In addition, we give a space lower bound of Ω(n^1-ε) for any randomized algorithm estimating the size of a maximum matching up to a 1+O(ε) factor for adversarial streams.

Citations

• The Factorization of Linear Graphs

Cited by

• A Dichotomy Theorem for Multi-Pass Streaming CSPs

Related

• Estimating Weighted Matchings in o(n) Space
• Weighted Matching in the Random-Order Streaming and Robust Communication Models
• Optimal Streaming Algorithms for Graph Matching
• On Estimating Maximum Matching Size in Graph Streams
• Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams