Mastering Approximation Algorithms: Lecture 2 (Paris, 2012) 📚

Lecture on Approximation Algorithms at the Parisian Computer Science Master<br />by Nicolas Schabanel<br />[ Session 2 Part B/B ]<br /><br />Lecture 2: Wed Oct 3, 2012 - 12:45-15:45<br /><br /> Linear Programming<br /> Introduction, LP Relaxation, First rounding (Vertex-Cover)<br /> Duality and Complementary Slackness Conditions<br /> Application: primal-dual algorithm for Vertex-Cover & Maximum/-al Matching<br /> (Note for next year: primal dual algorithm for Set-Cover would have been a better choice)