# SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?

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!

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