Separation guarantee in Goemans Williamson algorithm

In the original paper in Goemans-Williamson paper for max-cut, we need to sample a random vector r and we output $$S = \{i : r^{T}x_{i} \geq 0\}$$ where $$x_{i}$$ are column vector of a feasible solution of the SDP relaxation.

My question is are we guaranteed that there exists a certain $$r$$ such that the output is max-cut ?

• We are not guaranteed. The Goemans–Williamson algorithm is only an approximation algorithm. It's not guaranteed to produce a maximum cut. Apr 22 '20 at 19:38

Feige and Schechtman, On the optimality of the random hyperplane rounding technique for max cut, constructed a graph on which all $$r$$ only give an $$\alpha$$-approximation, where $$\alpha$$ is the worst-case approximation ratio of the Goemans–Williamson algorithm.