Learning-Augmented Algorithms for Online Vertex Cover

Online vertex cover is a classic problem where an algorithm must maintain a feasible vertex cover as vertices and edges are revealed over time, making irrevocable decisions. While worst-case competitive analysis is standard, it is often overly conservative. This paper investigates whether machine-learned advice can improve performance in this setting, specifically asking if the optimal robustness-consistency tradeoffs known for the ski rental problem can be achieved for online vertex cover.

The authors introduce a learning-augmented framework where, upon the arrival of each vertex, the algorithm receives a binary advice bit. This bit suggests whether to select the current vertex or all of its neighbors. The algorithm uses a tradeoff parameter λ to balance between the advice (consistency) and worst-case performance (robustness).

For bipartite graphs, the authors extend the water-filling algorithm by incorporating an advice-dependent threshold function. For general graphs, they employ a primal-dual framework where each vertex is assigned a dynamic trust threshold that adjusts based on the incoming advice. Both algorithms are designed to ensure that the total cost remains bounded relative to both the optimal offline solution and the advice-induced solution.

The paper establishes that the robustness-consistency tradeoffs for online vertex cover are identical to those of the ski rental problem. Specifically:

• For bipartite graphs, they provide a randomized algorithm with 1/(1-e^-λ) robustness and λ/(1-e^-λ) consistency.
• For general graphs, they provide a deterministic algorithm with (1 + 1/λ) robustness and (1 + λ) consistency.

The authors prove that these tradeoffs are mathematically optimal for their respective settings. Numerical experiments on synthetic and real-world datasets confirm that these algorithms outperform existing learning-augmented approaches and perform comparably to optimal competitive algorithms.