← 研踪 PaperTrailarXiv:2611.12210 · v1
Tight Competitive Bounds for Online Matching on Forests
首次提交 2026-11-09 19:05
版本更新 2026-11-09 19:05
雷达观测 2026-11-10 15:22
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 19:05 · 最新观测版本
Tight Competitive Bounds for Online Matching on Forests
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.
查看此版本解读 →查看此版本原文 ↗