Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

Yinhao Dong, Pan Peng, Ali Vakilian

We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$-approximation for estimating the va…