pipette
ESEspañol

A 1.764-competitive algorithm for online fractional vertex cover on forests

Marcin Bienkowski

Preprint

In the authors' words

We study online fractional vertex cover on forests under edge arrival. We give a deterministic algorithm with competitive ratio at most , which simultaneously produces an online fractional matching with competitive ratio of at least . This improves on the previous best competitive ratios of and , respectively.

Main resultThe abstract does not state a limitation.

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