# Learning-Augmented Algorithms for Online Vertex Cover

arXiv: https://arxiv.org/abs/2606.22831 · HTML: https://mlsanity.com/paper/2606.22831/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 22 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Learning-augmented Online Algorithm for Two-level Ski-rental Problem](https://mlsanity.com/paper/2402.06715/) (2024)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [Matroid Online Bipartite Matching and Vertex Cover](https://mlsanity.com/paper/1606.07863/) (2016)
- [Relaxing the Irrevocability Requirement for Online Graph Algorithms](https://mlsanity.com/paper/1704.08835/) (2017)

## Abstract (arXiv)

This paper studies learning-augmented online weighted vertex cover with local advice and a tradeoff parameter λ ∈ (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 frac11-e-λ-robust and fracλ1-e-λ-consistent. For the general graph model, we give a deterministic algorithm that is (1+frac1λ)-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.