Distinguished Lecture Series


"Approximation Algorithms: A Tour d'Horizon"

Michael X. Goemans, MIT

Thursday, February 26, 2009 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

Hard combinatorial 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 a few important tools in the algorithm designer's toolkit.

Michel Goemans is the Leighton Family Professor of Applied Mathematics at MIT, the Chairman of Applied Mathematics in MIT's Mathematics department, and a faculty member of MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). He was just named an ACM Fellow. He is also a Guggenheim Fellow, a Sloan Fellow and an Akamai Fellow. His research in combinatorial optimization and approximation algorithms has been rewarded with the AMS-MPS Fulkerson Prize, twice the SIAM Optimization prize, and the MPS Tucker prize. He has supervised 13 dissertations in computer science, applied mathematics and operations research at MIT.

A reception will follow in the atrium.

Host: Philip Klein

To see the poster for this lecture, please click here.