the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs. Another popular approach to obtain efficient approximations to NP-complete combinatorial optimization problems is that of sampling from a high enough temperature distribution using Markov chains. For the case of MAXCUT, this reduces to sampling from the Gibbs state on an Ising model. And there is a lot of literature which gives bounds on the temperatures that can be sampled from efficiently. However, I cannot find any comment on how SDP relaxations compare to polynomial-time Monte Carlo methods. What is the approximation ratio we obtain from Monte Carlo methods for say, 3 regular graphs? Any help is appreciated!

  • $\begingroup$ if you don't get an answer here, or.stackexchange.com might be a better bet, although it's a rather big "ask" there. $\endgroup$ Jul 21, 2020 at 1:27


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.