On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

None, None; None, None

On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

Journal Article (2020)

Author(s)

Fernando Mário de Oliveira Filho (TU Delft - Discrete Mathematics and Optimization)

Frank Vallentin (Universität zu Köln)

Semidefinite programming Integrality gap Maximum-cut problem

DOI related publication

https://doi.org/10.19086/da.14164 Final published version

To reference this document use

https://resolver.tudelft.nl/uuid:be85dd17-1c19-4440-9df2-f926b394b3e2

More Info

expand_more

Publication Year

2020

Language

English

Journal title

Discrete Analysis

Volume number

2020

Article number

10

Downloads counter

243

Abstract

We describe a factor-revealing convex optimization problem for the integrality gap of the maximum-cut semidefinite programming relaxation: for each n 2 we present a convex optimization problem whose optimal value is the largest possible ratio between the value of an optimal rank-n solution to the relaxation and the value of an optimal cut. This problem is then used to compute lower bounds for the integrality gap.