On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

Fernando Mário de Oliveira Filho; Frank Vallentin

doi:10.19086/da.14164

On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

Fernando Mário de Oliveira Filho, Frank Vallentin^*

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

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.

Original language	English
Article number	10
Number of pages	17
Journal	Discrete Analysis
Volume	2020
DOIs	https://doi.org/10.19086/da.14164
Publication status	Published - 2020

Keywords

Integrality gap
Maximum-cut problem
Semidefinite programming

Access to Document

10.19086/da.14164

Cite this

@article{be85dd171c1944409df2f926b394b3e2,

title = "On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension",

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.",

keywords = "Integrality gap, Maximum-cut problem, Semidefinite programming",

author = "{de Oliveira Filho}, {Fernando M{\'a}rio} and Frank Vallentin",

year = "2020",

doi = "10.19086/da.14164",

language = "English",

volume = "2020",

journal = "Discrete Analysis",

issn = "2397-3129",

publisher = "Alliance of Diamond OA Journals",

}

TY - JOUR

T1 - On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

AU - de Oliveira Filho, Fernando Mário

AU - Vallentin, Frank

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Integrality gap

KW - Maximum-cut problem

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=85115840453&partnerID=8YFLogxK

U2 - 10.19086/da.14164

DO - 10.19086/da.14164

M3 - Article

AN - SCOPUS:85115840453

SN - 2397-3129

VL - 2020

JO - Discrete Analysis

JF - Discrete Analysis

M1 - 10

ER -

On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this