arXiv:2611.12237 · v1

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

首次提交 2026-11-09 19:28

版本更新 2026-11-09 19:28

雷达观测 2026-11-10 15:22

摘要

We study online fractional vertex cover on forests under edge arrival. We give a deterministic algorithm with competitive ratio at most $4 - \sqrt{5} \approx 1.764$, which simultaneously produces an online fractional matching with competitive ratio of at least $1/(4 - \sqrt{5}) \approx 0.566$. This improves on the previous best competitive ratios of $11/6 \approx 1.833$ and $5/9 \approx 0.555$, respectively.