Authors: Alan Frieze, Mark Jerrum
Liked by: Maximimi
Domains: Optimisation
Tags: SDP
Uploaded by: Maximimi
Upload date: 2018-05-25 12:12:03

### Comments:

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
Maximimi at 2018-05-29 10:05:02
Edited by Maximimi at 2018-05-29 10:09:52

### Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. You can post public domain content. All user-generated content will be freely available online. Please see this page to learn more about Papersγ's terms of use and privacy policy.