On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension

Autor:	Filho, Fernando Mário de Oliveira, Vallentin, Frank
Rok vydání:	2018
Předmět:	Mathematics - Optimization and Control Computer Science - Data Structures and Algorithms 46N10 68W25 90C22
Zdroj:	Discrete Analysis, 2020:10
Druh dokumentu:	Working Paper
DOI:	10.19086/da.14164
Popis:	We describe a factor-revealing convex optimization problem for the integrality gap of the maximum-cut semidefinite programming relaxation: for each $n \geq 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. Comment: 17 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1808.02346 Zobrazit plný text záznamu View this record from Arxiv