Maximizing quadratic programs: Extending Grothendieck's inequality

Abstract

This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x ∈ {-1, 1}n such that xTAx is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in Ω(1/ log n). This quadratic programming problem can be seen as an extension to that of maximizing xTAy (where y's components are also ±1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from..