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


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

Please consider to register or login to comment on the paper.