Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model

DOI10.1137/100801901zbMath1237.05163OpenAlexW2762990162MaRDI QIDQ3225117

Leah Epstein, Danny Segev, Julián Mestre, Asaf Levin

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2476/

zbMATH Keywords

competitive analysisapproximation algorithmsweighted matchingsemi-streaming

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (16)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Superlinear lower bounds for multipass graph processing ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Improved bounds for randomized preemptive online matching ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Maximum matching on trees in the online preemptive and the incremental graph models

Uses Software

• TSPLIB

This page was built for publication: Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model