Computing the Grothendieck constant of some graph classes

DOI10.1016/J.ORL.2011.09.003zbMATH Open1235.90174arXiv1106.2735OpenAlexW2119747577MaRDI QIDQ408441FDOQ408441

Authors: Monique Laurent, A. Varvitsiotis 

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: Given a graph $G=([n],E)$ and $win{R}^E$, consider the integer program ${max}_{xin{pm1}^n}su{m}_{ijinE}{w}_{ij}{x}_i{x}_j$ and its canonical semidefinite programming relaxation $maxsu{m}_{ijinE}{w}_{ij}{v}_i^T{v}_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 a closed-form formula for the Grothendieck constant of $K_5$-minor free graphs and derive that it is at most 3/2. Moreover, we show that $ka(G)leka(K_k)$ if the cut polytope of $G$ is defined by inequalities supported by at most $k$ points. Lastly, since the Grothendieck constant of $K_n$ grows as $Theta(logn)$, it is interesting to identify instances with large gap. However this is not the case for the clique-web inequalities, a wide class of valid inequalities for the cut polytope, whose integrality ratio is shown to be bounded by 3.

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

Recommendations

• Quadratic forms on graphs (extended abstract)
• Quadratic forms on graphs
• Towards computing the Grothendieck constant
• Grothendieck-type inequalities in combinatorial optimization
• The Grothendieck constant of random and pseudo-random graphs

zbMATH Keywords

cut polytopeelliptopeGrothendieck constantclique-web inequality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Geometry of cuts and metrics
• Bell Inequalities, Grothendieck’s Constant, and Root Two
• On the cut polytope
• Quadratic forms on graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The real positive definite completion problem for a simple cycle
• The real positive semidefinite completion problem for series-parallel graphs
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Approximating the cut-norm via Grothendieck's inequality
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• Title not available (Why is that?)
• Grothendieck inequalities for semidefinite programs with rank constraint
• New Bell inequalities for the singlet state: Going beyond the Grothendieck bound
• Combinatorial properties and the complexity of a max-cut approximation
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

Cited In (5)

• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Quadratic forms on graphs
• Grothendieck-type inequalities in combinatorial optimization
• Computational Construction of W-graphs of Heeke algebras H(q, n) for nup to 15
• Quadratic forms on graphs (extended abstract)

This page was built for publication: Computing the Grothendieck constant of some graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408441)