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 repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.