skip to main | skip to sidebar

15-854B: Advanced Approximation Algorithms

http://www.cs.cmu.edu/~anupamg/adv-approx/
This material is based upon work supported by the National Science Foundation under Grant No. CCF-0747250. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

Saturday, January 26, 2008

Notes on Linear Programming

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.
Posted by Ryan O'Donnell at 4:50 PM

No comments:

Post a Comment

Newer Post Older Post Home
Subscribe to: Post Comments (Atom)

Blog Archive

  • ▼  2008 (55)
    • ►  April (10)
    • ►  March (11)
    • ►  February (15)
    • ▼  January (19)
      • Homework 2
      • Example for Primal-Dual fixed
      • Facility Location -- no joke
      • Some more LP notes
      • Notes on Linear Programming
      • Nina and Avrim's problem
      • You too can post to the blog
      • Homework 1 problem 4b correction
      • Homework 1 Clarification
      • Scribes and Math Writing
      • Lecture 3: 1 vs. 3/4 + eps hardness for Max-Covera...
      • Prepare for Tuesday's class
      • LP integrality gaps for Min-Set-Cover
      • Lecture 1 and Lecture 2 scribe notes posted
      • Why decision and search are different for approxim...
      • Lecture 2: Algorithms and gaps for Set-Cover and C...
      • Max-Coverage vs. Min-Set-Cover
      • Min-R^2-TSP
      • Lecture 1: Definitions; greedy algorithm for Set-C...
  • ►  2007 (1)
    • ►  November (1)