Universität zu Köln

de Oliveira Filho, Fernando Mario and Valleatin, Frank (2020). On the Integrality Gap of the Maximum-Cut Semidefinite Programming Relaxation in Fixed Dimension. Discrete Anal.. CAMBRIDGE: ALLIANCE DIAMOND OPEN ACCESS JOURNALS. ISSN 2397-3129

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code de Oliveira Filho, Fernando Mario UNSPECIFIED UNSPECIFIED UNSPECIFIED Valleatin, Frank UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-323888
DOI:	10.19086/da.14164
Journal or Publication Title:	Discrete Anal.
Date:	2020
Publisher:	ALLIANCE DIAMOND OPEN ACCESS JOURNALS
Place of Publication:	CAMBRIDGE
ISSN:	2397-3129
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Mathematics Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/32388