TY - JOUR

T1 - Quadratic forms on graphs

AU - Alon, Noga

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Naor, Assaf

PY - 2006/3/1

Y1 - 2006/3/1

N2 - We introduce a new graph parameter, called the Grothendieck constant of a graph G =(V,E), which is defined as the least constant K such that for every A : E → ℝ, supf:V → S|V|-1 ∑{u,v}∞E A(u,v) · 〈f(u),f(v)〉 ≤ K sup φ:V → {-1,+1} ∑{u,v}∞E A(u,v)· φ(u)φ(v). The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ⊃{u,v}∞E A(u,v)φ(u)φ(v) over all φ :V → {-1,1}, which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O(\logθ(Ḡ)), where θ(Ḡ) 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. We also show that the maximum possible integrality gap is always at least Ω(log∈ω(G)), where ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices with no loops is Θ(logn). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is Θ(logn). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.

AB - We introduce a new graph parameter, called the Grothendieck constant of a graph G =(V,E), which is defined as the least constant K such that for every A : E → ℝ, supf:V → S|V|-1 ∑{u,v}∞E A(u,v) · 〈f(u),f(v)〉 ≤ K sup φ:V → {-1,+1} ∑{u,v}∞E A(u,v)· φ(u)φ(v). The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ⊃{u,v}∞E A(u,v)φ(u)φ(v) over all φ :V → {-1,1}, which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O(\logθ(Ḡ)), where θ(Ḡ) 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. We also show that the maximum possible integrality gap is always at least Ω(log∈ω(G)), where ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices with no loops is Θ(logn). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is Θ(logn). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.

UR - http://www.scopus.com/inward/record.url?scp=32144451020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32144451020&partnerID=8YFLogxK

U2 - 10.1007/s00222-005-0465-9

DO - 10.1007/s00222-005-0465-9

M3 - Review article

AN - SCOPUS:32144451020

VL - 163

SP - 499

EP - 522

JO - Inventiones Mathematicae

JF - Inventiones Mathematicae

SN - 0020-9910

IS - 3

ER -