[MPRI 2012] Approximation Algorithms 3B

Lecture on Approximation Algorithms at the Parisian Computer Science Master
by Nicolas Schabanel
[ Lecture 3 Part B/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