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

DOI10.19086/da.14164zbMath1456.46064arXiv1808.02346MaRDI QIDQ5126773

Fernando Mário de Oliveira Filho, Frank Vallentin

Publication date: 20 October 2020

Published in: discrete Analysis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.02346

zbMATH Keywords

semidefinite programming; integrality gap; maximum-cut problem

Mathematics Subject Classification ID

90C22: Semidefinite programming

46N10: Applications of functional analysis in optimization, convex analysis, mathematical programming, economics

68W25: Approximation algorithms