All reports by Author Iannis Tourlakis:

__
TR06-152
| 6th December 2006
__

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis#### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

__
TR04-117
| 1st December 2004
__

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

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 >>>Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

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