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:
TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

TR16-010 | 28th January 2016
Alexander Razborov

On the Width of Semi-Algebraic Proofs and Algorithms

In this paper we initiate the study of width in semi-algebraic proof systems
and various cut-based procedures in integer programming. We focus on two
important systems: Gomory-Chv\'atal cutting planes and
Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for
proving width lower bounds and apply them to random $k$-CNFs and several ... more >>>

ISSN 1433-8092 | Imprint