Max-Cut with $\epsilon$-Accurate Predictions

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +2

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 give…