Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lovasz-Schrijver lift-and-project:
TR04-117 | 1st December 2004
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

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

TR06-152 | 6th December 2006
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>

ISSN 1433-8092 | Imprint