You may want to brush up on your linear programming; LP duality will be important for tomorrow's lecture.

For a relatively quick (40 pages) summary of the topic I usually go to Goemans's lecture notes. However these do not include the Ellipsoid Algorithm, which is of great theoretical importance for showing linear programming (and extensions, e.g., semidefinite programming) is in P.

For more details, Avner Magen's lecture notes look pretty thorough.

## Saturday, January 26, 2008

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment