Geodesic
On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension
Discrete analysis (2020) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

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.
Publié le : 
@article{DAS_2020_a10,
     author = {Fernando M\'ario de Oliveira Filho and Frank Vallentin},
     title = {On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension},
     journal = {Discrete analysis},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2020_a10/}
}
TY  - JOUR
AU  - Fernando Mário de Oliveira Filho
AU  - Frank Vallentin
TI  - On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension
JO  - Discrete analysis
PY  - 2020
UR  - http://geodesic.mathdoc.fr/item/DAS_2020_a10/
LA  - en
ID  - DAS_2020_a10
ER  - 
%0 Journal Article
%A Fernando Mário de Oliveira Filho
%A Frank Vallentin
%T On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension
%J Discrete analysis
%D 2020
%U http://geodesic.mathdoc.fr/item/DAS_2020_a10/
%G en
%F DAS_2020_a10
Fernando Mário de Oliveira Filho; Frank Vallentin. On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension. Discrete analysis (2020). http://geodesic.mathdoc.fr/item/DAS_2020_a10/