ECCC-Report TR05-058https://eccc.weizmann.ac.il/report/2005/058Comments and Revisions published for TR05-058en-usFri, 27 May 2005 18:00:20 +0300
Paper TR05-058
| On Non-Approximability for Quadratic Programs |
Sanjeev Arora,
Eli Berger,
Elad Hazan,
Guy Kindler,
Muli Safra
https://eccc.weizmann.ac.il/report/2005/058This paper studies the computational complexity of the following type of
quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as an intriguing connection to the famous {\em Grothendieck inequality} (Alon and Naor, 2004). It is approximable to within a factor of $O(\log n)$~\cite{nesterov,nemirovski,megretski,tony}, and known to be NP-hard to approximate within any factor better than $13/11 -\epsilon$ for all $\epsilon >0$~\cite{tony}. We show that it is quasi-NP-hard to approximate to a factor better than $O(\log^\gamma n)$ for some $\gamma>0$.
The integrality gap of the natural semidefinite relaxation for this problem is known as the {\em Grothendieck constant} of the complete graph, and known to be $\Theta(\log n)$ (Alon, K. Makarychev, Y. Makarychev and Naor, 2005~\cite{alonQP}). The proof of this fact was {\em 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 $\Omega(\frac{\log n}{\log \log n})$, essentially answering one of the open problems of \cite{alonQP}.
Fri, 27 May 2005 18:00:20 +0300https://eccc.weizmann.ac.il/report/2005/058