N&O seminar: Fernando Oliveira (TU Delft)

Everyone is welcome to attend the seminar on the integrality gap of the maximum-cut SDP relaxation in fixed dimension

Abstract:

For fixed $k \geq 4$ it is an open problem whether a rank-$k$ solution of the maximum-cut semidefinite programming relaxation can be rounded to a rank-1 solution with a better approximation ratio than that achieved by the Goemans-Williamson algorithm. I will discuss this problem and present a factor-revealing optimization problem whose optimal value is exactly the best possible approximation ratio for rounding a rank-$k$ solution. I will then show how this problem can be used to compute upper bounds on the best approximation ratio.

Joint work with Frank Vallentin.