Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
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. of STACS2008, pages 669-680) by devising a deterministic approach whose performance guarantee is 4.91+epsilon. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where …