Learning-Augmented Algorithms for Online Vertex Cover

Abstract:This paper studies learning-augmented online weighted vertex cover with local advice and a tradeoff parameter $\lambda \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^{-\lambda}}$-robust and $\frac{\lambda}{1-e^{-\lambda}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}{\lambda})$-robust and $(1+\lambda)$-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.

Computational Complexity (cs.CC); Machine Learning (cs.LG)

arXiv:2606.22831 [cs.CC]

(or arXiv:2606.22831v2 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2606.22831 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.