Distinguished Lecturer Series

Approximation Algorithms: A Tour d'Horizon

Michel X. Goemans

Leighton Family Professor of Applied Mathematics, MIT

Friday, October 17, 2008
10:30am - SENSQ 5317

Refreshments/meet the speaker at 10:00am

Hosted by Kirk Pruhs

Abstract

Hard optimization problems are ubiquitous in engineering and science. Because of their inherent complexity, there have been much interest in designing approximation algorithms --- efficient algorithms delivering solutions with a guarantee of suboptimality. This is a very active area and there have been several important developments in the last 15 years, both on the complexity side and on general techniques to design and analyze such algorithms. In this lecture, I will illustrate some of these developments, and describe some of the important tools in the algorithm designer's toolkit.

 

Biography of Speaker

Michel Goemans is a Professor of Applied Mathematics at the Massachusetts Institute of Technology, and a faculty member of MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and of MIT Operations Research Center (ORC). He has held an Adjunct Professorship at the University of Waterloo and a Professorship at the University of Louvain. His research --- in the areas of discrete algorithms and combinatorial optimization --- has been rewarded by several prizes, including the 2000 AMS-MPS Fulkerson Prize and twice the SIAM Optimization prize. 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.