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 - Electrical Engineering, Mathematics and Computer Science)
Frank Vallentin (Universität zu Köln)
Research Group
Discrete Mathematics and Optimization
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
expand_more
Publication Year
2020
Language
English
Research Group
Discrete Mathematics and Optimization
Journal title
Discrete Analysis
Volume number
2020
Article number
10
Downloads counter
332
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.