Max-Cut with ε-Accurate Predictions

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.