Seminars & Colloquia
Computer Science, Princeton University
"Semidefinite Programming and its applications to Approximation Algorithms"
Monday February 09, 2009 04:00 PM
Location: 3211, EB2 NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Triangle Computer Science Distinguished Lecturer Series
Computing approximately optimal solutions is an attractive way to cope with NP-hard optimization problems. In the past decade or so, semidefinite programming or SDP (a form of convex optimization that generalizes linear programming) has emerged as a powerful tool for designing such algorithms, and the last few years have seen a profusion of results (worst-case algorithms, average case algorithms, impossibility results, etc).
This talk will be a survey of this area and these recent results. We will see that analysing semidefinite program draws upon ideas from a variety of other areas, and has also led to new results in mathematics. At the end we will touch upon work that greatly improves the running time of SDP-based algorithms, making them potentially quite practical.
The survey will be essentially self-contained.
Sanjeev Arora is Professor of Computer Science at Princeton University and works in computational complexity theory, approximation algorithms for NP-hard problems, geometric algorithms, and probabilistic algorithms. He has received the ACM Doctoral Dissertation Award, the SIGACT-EATCS Goedel Prize, and the Packard Fellowship.
Host: Kamesh Munagala, Computer Science, Duke U.
To access the video of this talk, click here.
No media files available at this time