pipette
ENEnglish

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

Marcin Bienkowski

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

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