2011-11-01
Computing the Grothendieck constant of some graph classes
Publication
Publication
Operations Research Letters , Volume 39 - Issue 6 p. 452- 456
Given a graph G = ([n],E) and w ∈ R^E, consider the integer program max x∈{±1}^n \sum_{ij∈E} w_{ij} x_i x_j and its canonical semidefinite programming relaxation max \sum_{ij∈E} w_{ij} v_i^T v_j , where the maximum is taken over all unit vectors v_i ∈ R^n. The integrality gap of this relaxation is known as the Grothendieck constant K(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 K(G) ≤ K(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 O(log n), 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.
Additional Metadata | |
---|---|
, , , | |
North-Holland | |
Operations Research Letters | |
Spinoza prijs Lex Schrijver | |
Organisation | Networks and Optimization |
Laurent, M., & Varvitsiotis, A. (2011). Computing the Grothendieck constant of some graph classes. Operations Research Letters, 39(6), 452–456. |