Linear Programming 12: Minimum vertex cover

Linear Programming 12: Minimum vertex cover

Abstract: We describe how the minimum vertex cover problem can be setup as an integer linear programming problem. This is an integer program of intermediate difficulty, in the sense that the relaxed linear program approximates the optimal integer value within a factor of two.

This video accompanies the class "Linear Programming and Network Flows" at Colorado State University

We are following the book "Understanding and Using Linear Programming" by Jiří Matoušek and Bernd Gärtner

Our course notes are available at

[M_Nagy_]

I really like how you explain every move smoothly that makes it easy to understand. Thank you so much.

[mcyz]

awesome job for this kind of high level algorithm!

[yannisbekiaris]

Great explanation. can you saw us a tight example that achieves the 2-approximation?

[mahmoodalmohri]

Thank you for your demonstration. My question is that how do we assign the arbitrary value between 0 and 1 to each vertex? Earlier it was easier to do that, since I knew that if I chose the vertex to be in the vertex cover, then its value is one, and zero otherwise. But now how does each vertex get assigned their value?

[kulin]

Really good video, the only thing that I didn't get really clear is the criteria used for choosing a vertex when the value is greater or equal to 1/2, this value is stablished arbitrary or there is some kind of demonstration why we choose it? Thank you :)

[willywonka]

Thank you so much for the great explanation.. but is there any paper or article that proves that the approximation factor is 2 ? If so please give us any link .

[sarab]

Thanks for the explanation
Can you recommend for me a c++ code for Minimum vertex cover

[UniverseGames]

how do we define the 4-approximation problem?