# Improved Approximations for Hard Graph Problems using Predictions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 29 May 2025.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Approximation Algorithms for Combinatorial Optimization with Predictions](https://mlsanity.com/paper/2411.16600/) (2024)
- [Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems](https://mlsanity.com/paper/2402.02062/) (2024)
- [A centrality measure for quantifying spread on weighted, directed networks](https://mlsanity.com/paper/2303.09684/) (2023)
- [Constraint Satisfaction Problems with Advice](https://mlsanity.com/paper/2403.02212/) (2024)

## Built on by (most cited first, 4 of 4)

- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)
- [Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling](https://mlsanity.com/paper/2606.13133/) (2026)
- [Learning Augmented Exact Exponential Algorithms](https://mlsanity.com/paper/2606.18807/) (2026)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the varepsilon-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only varepsilon-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.