Advertising Console

    [MPRI 2012] Approximation Algorithms 4A

    Reposter
    Nicolas Schabanel

    par Nicolas Schabanel

    26
    130 vues
    Lecture on Approximation Algorithms at the Parisian Computer Science Master
    by Nicolas Schabanel
    [ Lecture 4 Part A/C ]

    Lecture 4: Wed Nov 7, 2012 - 12:45-15:45
    Hardness of approximation: The PCP theorem by GAP amplification
    1) A little bit of history
    2) Gap problems and Hardness of approximation
    3) The CSP: Graph Constraints Satisfaction Problem
    4) Overview of the Gap amplication process 2.a) definition
    5) A key tool: Expander graphs I
    6) Step 1: Degree uniformization
    7) Step 2: Expanderization
    8) Expander graphs II: spectral theory and random walks
    9) Step 3: Gap amplification
    10) Step 4 (last): Alphabet reduction
    11) Gap-preserving reductions

    Exercises session 4:
    1) Gap-preserving reductions for Vertex-Cover and Steiner Tree
    2) Random walks on expanders