2026-08-10T11:21:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2476 2024-03-06T10:33:24Z ddc:004 open_access

Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model Epstein, Leah Levin, Asaf Mestre, Julián Segev, Danny Approximation guarantees semi-streaming model one-pass algorithm We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study {\em preemptive} online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of $4.967$ on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leah Epstein and Asaf Levin and Julián Mestre and Danny Segev 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2476 urn:nbn:de:0030-drops-24766 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2476 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode