Logic List Mailing Archive

RAND-Seminar (Dept. of CS, Chair V)

RAND-Seminar / MPI-Seminar
--------------------------

Friday 20.12.2002  14:30
Seminar Room N327
Institute of Computer Science, Chair V
Roemerstr. 164 


Proving Integrality Gaps Without Knowing the Linear Program

Sanjeev Arora, Princeton University

Abstract:
Many approximation algorithms for NP-hard optimization 
problems are designed using a linear program relaxation of the problem. 
The integrality gap of the relaxation is the worst-case ratio of the 
cost of the optimum (integer) solution to the optimum value of the 
linear program. If we can show that the integrality gap is large, it 
rules out using that linear program for computing good approximations. 
 
Proving integrality gaps is a difficult task and usually undertaken on a 
case-by-case basis. We initiate a more systematic approach that proves 
integrality gaps for large families of linear programs. We prove an 
integrality gap of 2-o(1) for three families of relaxations for vertex 
cover, including those obtained from the Lovasz-Schrijver 
"lift-and-project" proof system. Our methods seem relevant to other 
problems as well. (Joint work with Bela Bollobas and Laszlo Lovasz)