Article ID Journal Published Year Pages File Type
1143254 Operations Research Letters 2011 5 Pages PDF
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
, ,