Name
Abstract | ||
|---|---|---|
We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality gap of 2, later strengthened by Hatami, Magen, and Markakis, for stronger relaxations that are, however, incomparable with two rounds of LS+. Subsequent work by Georgiou, Magen, Pitassi, and Tourlakis shows that the integrality gap remains 2 - \varepsilon after \Omega(\sqrt {\frac{{\log n}} {{\log \log n}}} ) rounds [?]. We prove that the integrality gap remains at least 7/6 - \varepsilon after c_{\varepsilon}n rounds, where n is the number of vertices and c_\varepsilon \ge 0 is a constant that depends only on \varepsilon. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/CCC.2007.2 | CCC '07 Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
linear programming,lovasz-schrijver sdp relaxations,integrality gap,lift-and-project method,linear round lower bound,semidefinite programming relaxations,standard linear programming relaxation,vertex cover,linear programming relaxation,lower bound,projection method | Discrete mathematics,Combinatorics,Upper and lower bounds,Vertex cover,Linear programming relaxation,Mathematics | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-2780-9 | 17 |
PageRank | References | Authors |
1.20 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Grant Schoenebeck | 1 | 509 | 39.48 |
| Luca Trevisan | 2 | 2995 | 232.34 |
| Madhur Tulsiani | 3 | 358 | 24.60 |