pipette
ENEnglish

Tight Competitive Bounds for Online Matching on Forests

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.