IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *

DOI10.4230/LIPIcs.STACS.2010.2476zbMath1230.68158OpenAlexW2145593504MaRDI QIDQ3113762

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

Publication date: 23 January 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_9cac.html

zbMATH Keywords

approximation guaranteessemi-streaming modelone-pass algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Maximum Matching in Turnstile Streams ⋮ Weighted matching in the semi-streaming model ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Buyback Problem - Approximate Matroid Intersection with Cancellation Costs ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Unnamed Item

Uses Software

• TSPLIB

This page was built for publication: IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *