用学习增强方法解决在线顶点覆盖问题，平衡鲁棒性与一致性。
Learning-Augmented Algorithms for Online Vertex Cover
- 基于局部提示和参数λ，设计新算法提升决策质量。
- 二分图下算法鲁棒性1/(1−e−λ)，一致性λ/(1−e−λ)。
- 适用于需要稳定与准确权衡的在线优化场景。
本文研究带局部提示和参数λ∈(0,1)的在线加权顶点覆盖问题。在二分图和一般图两种设定下，算法需在不可撤销决策中维持可行顶点覆盖。我们证明这些问题与学习增强滑雪租赁问题具有相同的鲁棒性-一致性权衡。对于二分图模型，提出一个随机算法，其鲁棒性为1/(1−e−λ)，一致性为λ/(1−e−λ)。对于一般图模型，给出一个确定性算法，鲁棒性为(1+1/λ)，一致性为(1+λ)。我们证明这些权衡在两种设定下均最优。实验在合成数据与真实世界数据集上验证了所提算法的有效性。
原文摘要 · Abstract (English)
This paper studies learning-augmented online weighted vertex cover with local advice and a tradeoff parameter $λ\in (0,1)$. We consider two graph settings: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is $\frac{1}{1-e^{-λ}}$-robust and $\fracλ{1-e^{-λ}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}λ)$-robust and $(1+λ)$-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。