loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Proving Integrality Gaps without Knowing the Linear Program
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Sanjeev Arora, Béla Bollobás, László Lovász, "Proving Integrality Gaps without Knowing the Linear Program," Foundations of Computer Science, Annual IEEE Symposium on, pp. 313, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181954,
author = {Sanjeev Arora and Béla Bollobás and László Lovász},
title = {Proving Integrality Gaps without Knowing the Linear Program},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {313},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181954},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Proving Integrality Gaps without Knowing the Linear Program
SN - 0272-5428
SP
EP
A1 - Sanjeev Arora,
A1 - Béla Bollobás,
A1 - László Lovász,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Sanjeev Arora, Princeton University
Béla Bollobás, University of Memphis
László Lovász, Microsoft Research
Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of 2 - o(1) for three families of linear relaxations for vertex cover, and our methods seem relevant to other problems as well.
Citation:
Sanjeev Arora, Béla Bollobás, László Lovász, "Proving Integrality Gaps without Knowing the Linear Program," focs, pp.313, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.