# Max-Cut with ε-Accurate Predictions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2024.

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

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization](https://mlsanity.com/paper/2511.19573/) (2025)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are given its correct label in -1,+1 with some unknown probability 1/2 + ε, and the other (incorrect) label otherwise. In the more-informative partial predictions model, for each vertex we are given its correct label with probability ε and no label otherwise. We assume only pairwise independence between vertices in both models. We show how these predictions can be used to improve on the worst-case approximation ratios for this problem. Specifically, we give an algorithm that achieves an α + widetildeOmega(ε4)-approximation for the noisy predictions model, where α ≈ 0.878 is the MaxCut threshold. While this result also holds for the partial predictions model, we can also give a β + Omega(ε)-approximation, where β ≈ 0.858 is the approximation ratio for MaxBisection given by Raghavendra and Tan. This answers a question posed by Ola Svensson in his plenary session talk at SODA'23.