Computing the Grothendieck constant of some graph classes

DOI10.1016/j.orl.2011.09.003zbMath1235.90174arXiv1106.2735OpenAlexW2119747577MaRDI QIDQ408441

Antonios Varvitsiotis, Monique Laurent

Publication date: 5 April 2012

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

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

zbMATH Keywords

cut polytopeelliptopeGrothendieck constantclique-web inequality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Grothendieck-Type Inequalities in Combinatorial Optimization, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• The real positive semidefinite completion problem for series-parallel graphs
• 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
• The real positive definite completion problem for a simple cycle
• Grothendieck inequalities for semidefinite programs with rank constraint
• New Bell inequalities for the singlet state: Going beyond the Grothendieck bound
• Approximating the cut-norm via Grothendieck's inequality
• On the Shannon capacity of a graph
• Bell Inequalities, Grothendieck’s Constant, and Root Two
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the cut polytope
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• Quadratic forms on graphs
• Geometry of cuts and metrics