N&O seminar: Fernando Oliveira (TU Delft)

Title: On the integrality gap of the maximum-cut SDP relaxation in fixed dimension
  • What Networks & Optimization English Seminars
  • When 03-10-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC200)
  • Where Room L016 at CWI, Science Park 123 in Amsterdam
  • Contact Name
  • Contact Phone 020-592 4189
  • Web Visit external website
  • Add event to calendar iCal

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.