N&O seminar: Fernando Oliveira (TU Delft)
Title: On the integrality gap of the maximum-cut SDP relaxation in fixed dimension
- https://www.cwi.nl/research/groups/networks-and-optimization/events/n-o-seminar-fernando-oliveira-tu-delft
- N&O seminar: Fernando Oliveira (TU Delft)
- 2018-10-03T11:00:00+02:00
- 2018-10-03T12:00:00+02:00
- 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 Susanne van Dam
- 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.