Advertising Console

    [MPRI 2012] Approximation Algorithms 3A

    Nicolas Schabanel

    par Nicolas Schabanel

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

    Lecture 3: Wed Oct 10, 2012 - 12:45-15:45
    A Polynomial Time Randomized Approximation Scheme (PTRAS) for dense Max-Cut
    1) Definition of PTAS, PTRAS, example of dependence in ε
    2) Dense Max-Cut
    2.a) definition
    2.b) the partition of the cut covers a constant fraction of the nodes
    3) A first algorithm
    3.a) A non-adaptative randomized sampling based algorithm
    3.b) An example on why it does not work
    4) The PTRAS
    4.a) Description of the algorithm
    4.b) Exhaustive guessing
    4.c) Hybridation
    4.d) Algorithmic analysis
    4.e) Probabilistic analysis
    4.f) Final theorem