Improved approximation guarantees for weighted matching in the semi-streaming model

Abstract

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. of STACS2008, pages 669-680) by devising a deterministic approach whose performance guarantee is 4.91+epsilon. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching.

Cited by in corpus (21)

• Buyback Problem - Approximate matroid intersection with cancellation costs
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• Kernelization via Sampling with Applications to Dynamic Graph Streams
• A $(2+\epsilon )$-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Improved Bounds for Online Preemptive Matching
• Tight Bounds for Linear Sketches of Approximate Matchings
• Online Matroid Intersection: Beating Half for Random Arrival
• Maximum Matching in Semi-Streaming with Few Passes
• Improved Bound for Matching in Random-Order Streams
• Single Pass Spectral Sparsification in Dynamic Streams
• Almost Optimal Streaming Algorithms for Coverage Problems
• Randomized Composable Coresets for Matching and Vertex Cover
• Simulating Random Walks on Graphs in the Streaming Model
• Distributed Weighted Matching via Randomized Composable Coresets
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
• Optimal Streaming Algorithms for Graph Matching
• Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models
• Maximum Coverage in the Data Stream Model: Parameterized and Generalized
• Substream-Centric Maximum Matchings on FPGA
• Communication complexity of approximate maximum matching in the message-passing model