Abstract
We consider the maximum weight bmatching problem in the randomorder semistreaming model. Assuming all weights are small integers drawn from [1,W], we present a 2  1/(2W) + ε approximation algorithm, using a memory of O(max(M_G, n) ⋅ poly(log(m),W,1/ε)), where M_G denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Aaron Bernstein, 2020], which achieves a 3/2 + ε approximation for the maximum cardinality simple matching. When W is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a 2  δ approximation (for some small constant δ ∼ 10^{17}) for the maximum weight simple matching. In particular, for the weighted bmatching problem, ours is the first result beating the approximation ratio of 2. Our technique hinges on a generalized weighted version of edgedegree constrained subgraphs, originally developed by Bernstein and Stein [Aaron Bernstein and Cliff Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a 2  1/(2W) + ε approximation of the maximum weight matching is proved using the classical KőnigEgerváry’s duality theorem.
BibTeX  Entry
@InProceedings{huang_et_al:LIPIcs.ESA.2022.68,
author = {Huang, ChienChung and Sellier, Fran\c{c}ois},
title = {{Maximum Weight bMatchings in RandomOrder Streams}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {68:168:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17006},
URN = {urn:nbn:de:0030drops170062},
doi = {10.4230/LIPIcs.ESA.2022.68},
annote = {Keywords: Maximum weight matching, bmatching, streaming, random order}
}
Keywords: 

Maximum weight matching, bmatching, streaming, random order 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 