Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

The little Grothendieck problem consists of maximizing ${\sum }_{ij}{C}_{ij}{x}_i{x}_j$ over binary variables $x_i\in \{\pm 1\}$, where C is a positive semidefinite matrix. In this paper we f…