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 (University of Cologne)
Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.19086/da.14164
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
Volume number
2020
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.
No files available
Metadata only record. There are no files for this record.