Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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 ?
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.
