Sanjeev Arora

Princeton University

Semidefinite programming and approximation algorithms: A survey of recent results

 

 

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.

 

****************

 

4:15pm

B17 Upson Hall

Thursday, December 4, 2008

Refreshments at 3:45pm in the Upson 4th Floor Atrium

Computer Science

Colloquium

Fall 2008

www.cs.cornell.edu/events/colloquium