On non-approximability for quadratic programs

Sanjeev Arora, Eli Berger, Elad E. Hazan, Guy Kindler, Muli Safra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x ε {-1,1} n that maximizes x TMx. 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 approximate to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - ε for all ε > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log γ n)for some γ > 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 ⊖(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 Ω(log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages206-215
Number of pages10
DOIs
StatePublished - Dec 1 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'On non-approximability for quadratic programs'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Berger, E., Hazan, E. E., Kindler, G., & Safra, M. (2005). On non-approximability for quadratic programs. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 (pp. 206-215). [1530715] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.57