Papers^γ

Great SDP relaxation of max-k-cut and max-bisection: very inspiring! ### Complicated analysis: The analysis to prove the approximation guarantee is quite complicated though. Much more complicated than the one of [the Goemans-Williamson algorithm](https://en.wikipedia.org/wiki/Semidefinite_programming#Example_3) for max-cut. Is a simpler analysis possible? Or another relaxation leading to a simpler analysis having similar or better approximation guarantees? ### Implementing the algorithms in a scalable way: How can we implement such an algorithm in a scalable way? Say for a sparse graph with 1M nodes and 100M edges? For Goemans-Williamson, this is a try: https://github.com/maxdan94/spingraphSDP