pipette
ESEspañol

Tight Competitive Bounds for Online Matching on Forests

Bart{\l}omiej Bosek, Grzegorz Gutowski, Pawe{\l} Putra, Anna Zych-Pawlewicz

Preprint

In the authors' words

We study the online matching problem, its fractional relaxation, and the fractional online vertex cover problem on forests whose edges arrive one at a time in an arbitrary order. Matching decisions are irrevocable, and vertex-cover weights can only increase over time. For online matching, we present a randomized algorithm with expected competitive ratio against an oblivious adversary, improving the previous guarantee. We also present a deterministic algorithm that simultaneously maintains a -competitive fractional matching and a -competitive fractional vertex cover. This deterministic algorithm improves the previous guarantee for fractional matching and the guarantee for fractional vertex cover. We prove that is optimal for both randomized and fractional matching, even on growing trees of maximum degree four.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.