Moses Charikar
Department of Computer Science
Princeton University
"New Insights into Semidefinite Programming for Combinatorial Optimization"
Beginning with the seminal work of Goemans and Williamson on Max-Cut, semidefinite programming (SDP) has firmly established itself as an important ingredient in the toolkit for designing approximation algorithms for NP-hard problems. Algorithms designed using this approach produce configurations of vectors in high dimensions which are then converted into actual solutions.
In recent years, we have made several strides in understanding the power as well as the limitations of of such SDP approaches. New insights into the geometry of these vector configurations have led to algorithmic breakthroughs for several basic optimization problems. At the same time, a sequence of recent results seems to suggest the tantalizing possibility that, for several optimization problems including Max-Cut, SDP approaches may indeed be the best possible. In this talk, I will present a glimpse of some of this recent excitement around SDP-based methods and explain some of the new insights we have developed about the strengths and weaknesses of this sophisticated tool.
The talk will be self-contained and no background will be assumed.
Thursday, February 19, 2009
3:00 - 4:15
Berger Auditorium, Skirkanich Hall
210 South 33rd Street