Improved Bounds for Online Preemptive Matching

摘要: When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain valid M while edges of underlying graph are presented one after other. with an edge e, should decide whether augment by adding e (in which case may be removed later on) or keep in its current form without is lost good). The objective eventually hold weight. The main contribution this paper establish new lower and upper bounds on competitive ratio achievable algorithms: - We provide bound 1 + ln 2 \approx 1.693 any randomized cardinality thus improving currently best known / (e-1) 1.581 due Karp, Vazirani, Vazirani [STOC'90]. - devise that achieves expected 5.356 weight matching. This finding demonstrates power randomization context, showing how beat tight 3 2\sqrt{2} 5.828 deterministic algorithms, obtained combining McGregor [APPROX'05] recent Varadaraja [ICALP'11].