grothendieck constant

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

  • Marianna Eisenberg-Nagy
  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , , ,

    We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of … Read more

    Computing the Grothendieck constant of some graph classes

  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Given a graph $G=([n],E)$ and $w\in\R^E$, consider the integer program ${\max}_{x\in \{\pm 1\}^n} \sum_{ij \in E} w_{ij}x_ix_j$ and its canonical semidefinite programming relaxation ${\max} \sum_{ij \in E} w_{ij}v_i^Tv_j$, where the maximum is taken over all unit vectors $v_i\in\R^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\ka(G)$ of $G$. We present … Read more