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
More Info
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.