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

Arora, S., Bollobás, B., & Lovász, L. (2002). Proving integrality gaps without knowing the linear program.

*Annual Symposium on Foundations of Computer Science - Proceedings*, 313-322.