A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model

DOI10.1145/3274668zbMath1454.68187OpenAlexW2904319175MaRDI QIDQ4629986

Ami Paz, Gregory Schwartzman

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3274668

zbMATH Keywords

matchingsapproximation algorithmslocal-ratiosemi-streaming algorithms

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) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams

This page was built for publication: A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model