Uploaded June 2020 | Updated November 2026, 2 days ago
Finding an approximately minimum Vertex-Cover: First exactly capture the Min-Vertex-Cover with an ILP, then relax it to an LP and solve. Finally, "round" the fractional solution to an integer one, in this case of cost no more than 2x the LP cost and hence no more than 2x the minimal cost. Lecture 18c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture:
"Understanding and Using Linear Programming" by Matoušek and Gärtner
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)
Finding an approximately minimum Vertex-Cover: First exactly capture the Min-Vertex-Cover with an ILP, then relax it to an LP and solve. Finally, "round" the fractional solution to an integer one, in this case of cost no more than 2x the LP cost and hence no more than 2x the minimal cost. Lecture 18c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture:
"Understanding and Using Linear Programming" by Matoušek and Gärtner
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)










