2
$\begingroup$

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 ?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.