M2-(9 a 12 hs) Approximation Algorithms

Profesor: Julian Mestre. Max-Planck-Institut for Informatik. (en castellano)

http://www.mpi-inf.mpg.de/~jmestre/

Abstract: Combinatorial optimization problems are pervasive and arise in nearly every application area. These problems typically ask for a combinatorial structure of minimum cost obeying a number of constraints; for example, in the travelling salesman problem (TSP) we are to find a minimum length tour visiting a set of point on the plane. Because of their discrete nature, finding an optimal solution for these problems is usually trivial; for example, in the TSP we could try all possible permutations of the points and keep the best. However, the fact that the number of possible solutions normally grows exponentially with the size of the input instance renders this brute-force approach infeasible even for small instances. Therefore it is critical to have algorithms that are efficient; namely, their running time should be polynomial on the size of the input instance. Unfortunately, the theory of NP-completeness strongly suggests that for a large number of optimization problems of practical interest, there may not be efficient algorithms. Approximation algorithms represent an attempt to deal with this hardness. The basic idea is to relax the requirement that the solution be optimal, settling instead for solutions close to optimum. For example, even though we may not be able to nd the optimal TSP tour, there are efficient algorithms that are guaranteed to return a solution that is atmost, say, 2% more expensive than the best possible tour.The objective of this course is to introduce students to the exciting area of approximation algorithms. Each lecture will cover a couple of basic techniques commonly used in the design of approximations. Even though lectures will be centered around problem-specific results, we will always emphasize the underlying principles at work.