[MPRI 2012] Approximation Algorithms 2A

Lecture on Approximation Algorithms at the Parisian Computer Science Master
by Nicolas Schabanel
[ Session 2 Part A/B ]

Lecture 2: Wed Oct 3, 2012 - 12:45-15:45

Linear Programming
Introduction, LP Relaxation, First rounding (Vertex-Cover)
Duality and Complementary Slackness Conditions
Application: primal-dual algorithm for Vertex-Cover & Maximum/-al Matching
(Note for next year: primal dual algorithm for Set-Cover would have been a better choice)