Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143254 | Operations Research Letters | 2011 | 5 Pages |
Abstract
The Grothendieck constant κ(G) of a graph G=([n],E) is the integrality gap of the canonical semidefinite relaxation of the integer program maxxâ{±1}nâijâEwijxiâ
xj, replacing ±1 variables by unit vectors. We show that κ(G)=g/(gâ2)cos(Ï/g)â¤3/2 when G has no K5-minor and girth g; moreover, κ(G)â¤Îº(Kk) if the cut polytope of G is defined by inequalities supported by at most k points; lastly the worst case ratio of clique-web inequalities is bounded by 3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
M. Laurent, A. Varvitsiotis,