[MPRI 2012] Approximation Algorithms 1A

Lecture on Approximation Algorithms at the Parisian Computer Science Master
by Nicolas Schabanel
[ Session 1 Part A/B ]

Session 1: Wed Sep 26, 2012 - 12:45-15:45
1) Introduction to Approximation Algorithms
* P vs NP, a refinement of NP-completeness: Inapproximability results
* Definitions of Optimization problems and Approximation algorithms
* General principles for obtaining approximation algorithms

2) An exemplary example: the Travelling Salesman Problem
* Definition of TSP
* Inapproximability of general TSP unless P = NP
* A first 2-approximation algorithm (MST-based)
* Cristofides algorithm: a 3/2-algorithm
* Family of tight instances for both algorithms