minicourses TU/e code: 2E941 1 ECTS

5-day minicourse on Approximation Algorithms Prof. Michel Goemans Massachusetts Institute of Technology, USA March 27 - 31, 2006

Prof. Michel X. Goemans received his Ph.D. in 1990 from MIT, where he is now a Professor of Applied Mathematics. He has held a professorship at the Université Catholique de Louvain and an adjunct professorship at the University of Waterloo. His research interests are in mathematical programming and theoretical computer science, and especially in algorithmic, structural and polyhedral aspects of combinatorial optimization problems. His awards include the Fulkerson prize, twice the SIAM Optimization prize, the Tucker prize and a Sloan fellowship. He has been an invited speaker at many conferences, including the International Congress of Mathematicians in 1998. He has been on the program committee of several major theoretical computer science conferences, including as chair of the 2003 Symposium on Theory of Computing.

Contents
Due to the NP-hardness of many combinatorial optimization problems, there has been much interest in designing approximation algorithms --- polynomial-time algorithms delivering solutions with a guarantee of suboptimality. This is a very active area and there have been many developments in the last 15 years, both on the complexity side (limits to approximability) and on general techniques to design and analyze such algorithms.

In this series of lectures, I will discuss some recent approximation results, with an emphasis on the techniques used. Among several other topics, the lectures will cover the approximation of the sparsest cut problem through metric embeddings, the use of matroid intersection for bounded-degree spanning trees, the approximation of stochastic variants of combinatorial optimization problems and the latest progress on the maximum cut problem. The mini-course will be self-contained.

Time and Place
Technische Universiteit Eindhoven, The Netherlands
March 27 - 31, 2006.

Admission fee,
The admission fee for a minicourse is EUR 300 for university staff members and PhD students, and EUR 500 for people from industry. EIDMA and DIAMANT members receive a reduction of EUR 100 on these amounts. For undergraduate students special conditions apply. For the exact conditions please see the course registration form.

Registration
You can register by sending a completed registration form to ms. Henny Houben at eidma@tue.nl.
Deadline for registration is March 10, 2006.
Please note that your registration is only official after our written confirmation of its receipt.