On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms

Haoyan Shi, Sanjay Mehrotra

Goemans and Williamson proposed a randomized rounding algorithm for the MAX-CUT problem with a 0.878 approximation bound in expectation. The 0.878 approximation bound remains the b…