Learning-Augmented Algorithms for Online Vertex Cover (opens in new tab)

This paper studies learning-augmented online weighted vertex cover with advice and a parameter $\lambda \in (0,1)$. We consider two graph cases: 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 randomi...