Computing the Grothendieck constant of some graph classes

Monique Laurent, Antonios Varvitsiotis

Given a graph $G=([n],E)$ and $w\in {\mathbb{R}}^E$, consider the integer program ${\max }_{x\in \{\pm 1{\}}^n}{\sum }_{ij\in E}{w}_{ij}{x}_i{x}_j$ and its canonical semidefinite programming relaxatio…