Quadratic forms on graphs and their applications
Konstantin Makarychev · 2008
We study the following quadratic optimization problem. MAX QP: Given a real matrix aij, maximize the quadratic form aij · xixj, ij where variables xi take values ±1. We show that the integrality gap of the natural SDP relaxation depends on the structure of the support of the matrix A. We define a new graph parameter, the Grothendieck constant of a graph G = (V, E), to be the worst integrality gap among matrices A with support restricted to the edges of G (i.e. we require that if (i, j) / ∈ E, then aij = 0). We give upper and lower estimates for the Grothendieck constant of the graph G: We show that it is less than O(log ϑ ( ¯ G)), where ϑ ( ¯ G) is the Lovász theta function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G.