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

Leah Epstein, Asaf Levin, Julián Mestre & Danny Segev
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...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.