Proving integrality gaps without knowing the linear program

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

Research output: Contribution to journalConference article

59 Scopus citations

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 languageEnglish (US)
Pages (from-to)313-322
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 2002
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this