Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$.

What is known about the distribution on such cuts, as induced by the hyperplane randomized rounding procedure?

For example, is it known whether or not $S$ is distributed uniformly over the cuts of size at least $1-\sqrt{\epsilon}$.

To place in context, it is known for example, that if one allows $\Omega(n)$ levels of SDP / Lasserre relaxations, then one can force the output distribution to be uniformly random on the set of exact MAX-CUTS, so essentially the question is whether or not such behavior holds in a similar way for lower-level (and efficiently-computable) levels of SDP.

  • $\begingroup$ Considering $1-\epsilon$ vs $1-\sqrt \epsilon$ doesn't really make sense unless you are normalizing in some particular way. What normalization do you have in mind here? E.g. I could multiply all edge weights by $1/(1-\epsilon)$, then I would have $\text{maxcut}(G) \ge 1$, but presumably the rounding procedure would not return a cut of size at least $1$. Also, what do you mean by "fractional size"? $\endgroup$ – Neal Young Mar 4 '18 at 21:56

Your Answer

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

Browse other questions tagged or ask your own question.