Advertising Console

    [MPRI 2012] Approximation Algorithms 2A

    Nicolas Schabanel

    par Nicolas Schabanel

    177 vues
    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)