Advertising Console

    [MPRI 2012] Approximation Algorithms 1A

    Nicolas Schabanel

    par Nicolas Schabanel

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

    Session 1: Wed Sep 26, 2012 - 12:45-15:45
    1) Introduction to Approximation Algorithms
    * P vs NP, a refinement of NP-completeness: Inapproximability results
    * Definitions of Optimization problems and Approximation algorithms
    * General principles for obtaining approximation algorithms

    2) An exemplary example: the Travelling Salesman Problem
    * Definition of TSP
    * Inapproximability of general TSP unless P = NP
    * A first 2-approximation algorithm (MST-based)
    * Cristofides algorithm: a 3/2-algorithm
    * Family of tight instances for both algorithms