Mastering Approximation Algorithms: Lecture 3B by Nicolas Schabanel 📚

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