Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION
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

You comment anonymously! You will not be able to edit/delete the comment.

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. All data you give us will be freely available online. You can post any public domain content. Please see this page to learn more about us, Papersγ's terms of use and privacy policy.