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

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

## Comments:

Edited by Maximimi at 2018-05-29 10:09:52