Opening Rounding LP Solutions: Minimum Vertex Cover
Rounding LP Solutions: Minimum Vertex Cover
- Length
- 18 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Minimum vertex cover problem
Minimum-cost vertex cover is NP-hard, and O'Donnell opens by showing a simple greedy heuristic failing badly on weighted graphs. He then writes the problem exactly as an integer linear program, with one variable per vertex and one constraint per edge. Relaxing each variable to the interval gives a linear program solvable in polynomial time, whose optimum bounds the true cost from below. Taking every vertex with fractional value at least yields a valid cover costing at most twice the LP value, hence at most twice the optimum. The session is lecture 18c of CMU 15-750, A Theorist's Toolkit, and assumes graph theory, linear programming and NP-hardness.

Your comment is kept while you sign up.Sign in
O'Donnell relaxes the vertex cover integer program to an LP, then rounds at one half to get a 2-approximation.
Minimum-cost vertex cover is NP-hard, and O'Donnell opens by showing a simple greedy heuristic failing badly on weighted graphs. He then writes the problem exactly as an integer linear program, with one variable per vertex and one constraint per edge. Relaxing each variable to the interval gives a linear program solvable in polynomial time, whose optimum bounds the true cost from below. Taking every vertex with fractional value at least yields a valid cover costing at most twice the LP value, hence at most twice the optimum. The session is lecture 18c of CMU 15-750, A Theorist's Toolkit, and assumes graph theory, linear programming and NP-hardness.
This lecture
Lecture 58 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.