A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

DOI10.1137/1.9781611974782.140zbMath1410.68403arXiv1702.04536OpenAlexW3100080045MaRDI QIDQ4575888

Ami Paz, Gregory Schwartzman

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.04536

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items

Unnamed Item ⋮ Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Improved bounds for randomized preemptive online matching ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs