Proving integrality gaps without knowing the linear program

Sanjeev Arora; Béla Bollobás; László Lovász

Proving integrality gaps without knowing the linear program

Sanjeev Arora, Béla Bollobás, László Lovász

Research output: Contribution to journal › Conference article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	313-322
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - Dec 1 2002
Event	The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Cite this

@article{ac6bc220a90b4daa9819d5baa8d80e26,

title = "Proving integrality gaps without knowing the linear program",

abstract = "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.",

author = "Sanjeev Arora and B{\'e}la Bollob{\'a}s and L{\'a}szl{\'o} Lov{\'a}sz",

year = "2002",

month = dec,

day = "1",

language = "English (US)",

pages = "313--322",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "The 34rd Annual IEEE Symposium on Foundations of Computer Science ; Conference date: 16-11-2002 Through 19-11-2002",

}

TY - JOUR

T1 - Proving integrality gaps without knowing the linear program

AU - Arora, Sanjeev

AU - Bollobás, Béla

AU - Lovász, László

PY - 2002/12/1

Y1 - 2002/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0036953711&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036953711&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0036953711

SN - 0272-5428

SP - 313

EP - 322

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - The 34rd Annual IEEE Symposium on Foundations of Computer Science

Y2 - 16 November 2002 through 19 November 2002

ER -

Proving integrality gaps without knowing the linear program

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Cite this