Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-117 | 1st December 2004 00:00

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy


Authors: Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
Publication: 16th December 2004 16:13
Downloads: 2858


Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such as MAX-3SAT, Hypergraph Vertex Cover and Minimum Set Cover. We show that the relaxations produced by as many as $\Omega(n)$ rounds of the LS+ procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS+ approach gives even slightly subexponential approximation algorithms for these problems.

We also point out why our results are somewhat incomparable to known nonapproximability results proved using PCPs, and formalize several interesting open questions.

ISSN 1433-8092 | Imprint