Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.4086/toc.2006.v002a002 | Theory of Computing |
Keywords | DocType | Volume |
inapproximability,vertex cover,linear programming,integrality gaps,approximation algorithms,lift-and-project,np-hard problems,linear program,optimization problem | Journal | 2 |
Issue | Citations | PageRank |
1 | 38 | 1.73 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjeev Arora | 1 | 4508 | 379.31 |
| Béla Bollobás | 2 | 2696 | 474.16 |
| László Lovász | 3 | 791 | 152.09 |
| Iannis Tourlakis | 4 | 157 | 10.16 |