Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ELI BERGER:
All reports by Author Eli Berger:

TR05-058 | 24th May 2005
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

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 \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 ... more >>>




ISSN 1433-8092 | Imprint