Seminar Series Archive

Optimization problems are pervasive in a wide range of industries, and finding the best solution is typically hard from a computational complexity point of view. The theoretician when facing with a challenging optimization problem would often simplify the model and turn to designing approximation algorithms; there are efficient or polynomial-time algorithms that return a solution with an a priori label of quality. The practitioner would often dismiss these efforts as impractical and of little value to the problem being considered.

In this talk, I will provide my perspectives on the design of approximation algorithms for hard optimization problems. What makes them practical or impractical? What is their theoretical value? What are some of the underlying design ideas and techniques? I will try to address these questions, and illustrate related concepts using both classical results in the field and also some of my favorite longstanding open problems.

Michel Goemans received his undergraduate degree from UCLouvain in Belgium, and his Ph.D. at MIT in 1990. He also holds an Honorary Doctorate from UC Louvain. He has been a faculty member in the Department of Mathematics at MIT since 1992, and was the inaugural holder of the Leighton Family Chair in Mathematics. He is currently devoting much of his time as Head of the Mathematics Department.

His research interests are in Algorithms, Combinatorics and Optimization, and has obtained various techniques to design and analyze approximation algorithms, including the use of semidefinite programming.

He has received the Fulkerson Prize, twice the SIAM Optimization Prize, a Guggenheim Fellowship, and the Farkas Prize. He is a fellow of ACM, AMS, and SIAM.