A 1.764-competitive algorithm for online fractional vertex cover on forests
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.