Quadratic Forms on Graphs and Their Applications. (Paperback)

We study the following quadratic optimization problem. MAX QP: Given a real matrix aij, maximize the quadratic form ijaij˙x ixj, 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 theta( G)), where theta(G) is the Lovasz 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. We prove that the Grothendieck constant is always at least C log w(G), where w( G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices is C log n. We present approximation algorithms for the MAX k-CSP and ADVANTAGE OVER RANDOM FOR MAXIMUM ACYCLIC SUBGRAPH problems. These algorithms solve the MAX QP problem at an intermediate step and then use the obtained solution to solve more complex combinatorial problems.