| Date: | 15:30-17:00, Wednesday, April 15, 2009 |
| Venue: | FIT Building 1-222, Tsinghua University |
| Title: | New Insights into Semidefinite Programming for Combinatorial Optimization |
| Speaker: | Prof. Moses Charikar, Dept. of Computer Science,Princeton University |
| Biography: |
Moses Charikar is an Associate Professor of Computer Science at Princeton University. He received his B.Tech from IIT Bombay and his Ph.D. from Stanford University. He spent a year in the research group at Google and has been at Princeton since. His research interests are in algorithm design and analysis, particularly in approximation algorithms, the study of metric embeddings and algorithmic techniques for large data sets.
|
|
|
|
| Abstract: |
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. |
