2026-07-19T22:17:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4690 2024-03-06T10:35:14Z ddc:004 open_access

Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching Crouch, Michael Stubbs, Daniel M. Streaming Algorithms Graph Matching Weighted Graph Matching MapReduce Independence Systems We present a (4 + epsilon) approximation algorithm for weighted graph matching which applies in the semistreaming, sliding window, and MapReduce models; this single algorithm improves the previous best algorithm in each model. The algorithm operates by reducing the maximum-weight matching problem to a polylog number of copies of the maximum-cardinality matching problem. The algorithm also extends to provide approximation guarantees for the more general problem of finding weighted independent sets in p-systems (which include intersections of p matroids and p-bounded hypergraph matching). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Crouch and Daniel M. Stubbs 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.96 urn:nbn:de:0030-drops-46907 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.96 eng https://creativecommons.org/licenses/by/3.0/legalcode