Mastering Approximation Algorithms: Lecture from Paris CS Master (2012) 📚

Lecture on Approximation Algorithms at the Parisian Computer Science Master<br />by Nicolas Schabanel<br />[ Session 1 Part A/B ]<br /><br />Session 1: Wed Sep 26, 2012 - 12:45-15:45<br /> 1) Introduction to Approximation Algorithms<br /> * P vs NP, a refinement of NP-completeness: Inapproximability results<br /> * Definitions of Optimization problems and Approximation algorithms<br /> * General principles for obtaining approximation algorithms<br /><br /> 2) An exemplary example: the Travelling Salesman Problem<br /> * Definition of TSP<br /> * Inapproximability of general TSP unless P = NP<br /> * A first 2-approximation algorithm (MST-based)<br /> * Cristofides algorithm: a 3/2-algorithm<br /> * Family of tight instances for both algorithms