[2016 MPRI 2.11.1] 1. Introduction to Approximation Algorithms (2016/9/14)

MPRI - Parisian Master of Research in Computer Science
Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming
Nicolas SCHABANEL, CNRS - Université Paris Diderot

LECTURE 1 (2016/09/14)
INTRODUCTION TO APPROXIMATION ALGORITHMS

[0:00:00] 0. Introduction to the Course
[0:09:10] 1. Optimization problems & Approximation Algorithms
[0:31:24] 2. About Hardness of approximation
[1:06:03] 3. Approximation Algorithms for Metric TSP
[1:33:28] 4. Exercice: 3/2-Approximation for Metric TSP
[2:25:03] 5. Exercise: Maximum Arc-Disjoint Paths (1)