On Non-Approximability for Quadratic Programs

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

Authors

• Sanjeev Arora
• Eli Berger
• Elad Hazan
• Guy Kindler
• Muli Safra

Keywords

• Computer science
• Clustering algorithms
• Approximation algorithms
• Linear matrix inequalities
• Computational complexity
• Quadratic programming
• Physics
• Glass
• Context modeling
• Polynomials
• Set Of Equations
• Nonlinear Optical
• Coefficient Functions
• Fourier Series
• Diagonal Entries
• Real-valued Function
• Combined Form
• Fourier Coefficients
• Sound Properties
• Integral Solution
• Boolean Function
• External Form