Optimization Online


Grothendieck inequalities for semidefinite programs with rank constraint

Jop Briet(j.briet***at***cwi.nl)
Fernando M. de Oliveira Filho(F.M.deOliveiraFilho***at***uvt.nl)
Frank Vallentin(f.vallentin***at***tudelft.nl)

Abstract: Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: A difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we consider Grothendieck inequalities for ranks greater than 1 and we give one application in statistical mechanics: Approximating ground states in the n-vector model.

Keywords: Grothendieck inequality, n-vector model, randomized rounding

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 11/08/2010
Entry Accepted: 11/08/2010
Entry Last Modified: 11/08/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society