Advanced Algorithms: Linear and Semidefinite Programming (original) (raw)

Lecturers: Anupam Gupta and Ryan O'Donnell

Time: TR 12:00-1:20, GHC 4303

Course Blog: http://lpsdp.wordpress.com/

Office Hours: by appointment

Homework:

Homework 1 (due Thursday, September 22) and exercises (solutions)
Homework 2 (due Thursday, September 29) and exercises (solutions)
Homework 3 (due Tuesday, October 11) (solutions)
Homework 4 (due Thursday, October 20)
Homework 5 (due Thursday Tuesday, November 15)
Homework 6 (due Tuesday, December 6)

(Solutions accessible only from CMU/Pitt.)

Scribe notes:

How to scribe

• All notes so far
• Lecture 1: Linear Programming Intro: An Algebraic View (AG; Jamie Morgenstern scribe)
• Lecture 2: Linear Programming Intro: A Geometric View (AG; Brian Kell scribe)
• Lecture 3: LP examples: Max-Flow, Matching, Vertex-Cover (RO; Will Devanny scribe)
• Lecture 4: The Simplex Method (RO; Aaron Snook scribe)
• Lecture 5: LP Duality (AG; Tim Wilson scribe)
• Lecture 6: Applications of LP Duality (AG; Deepak Bal scribe)
• Lecture 7: Applications of LP Duality (II) (AG; Carol Wang scribe)
• Lecture 8: The Ellipsoid Algorithm for LP feasibility (RO; Srivatsan Narayanan scribe)
• Lecture 9: More on Ellipsoid: Grötschel-Lovász-Schrijver theorems (RO; John Wright scribe)
• Lecture 10: Semidefinite Programs and the Max-Cut Problem (RO; Franklin Ta scribe)
• Lecture 11: The Lovász Theta Function (AG; David Witmer scribe)
• Lecture 12: Semidefinite Duality (AG; Alex Beutel scribe)
• Lecture 13: The Canonical LP for Constraint Satisfaction Problems (RO; Ravishankar Krishnaswamy scribe)
• Lecture 14: The Canonical SDP for CSPs (RO; Jamie Morgenstern scribe)
• Lecture 15: Rounding SDPs for CSPs (RO; Brian Kell scribe)
• Lecture 16: The Multiplicative Weights Algorithm (AG; Shiva Kaul scribe)
• Lecture 17: Solving LPs/SDPs using Multiplicative Weights (AG; Tim Wilson scribe)
• Lecture 18: Low-Dimensional Linear Programming (AG; Srivatsan Narayanan scribe)
• Lecture 19: Improved Approximations for TSP Path (RO; David Witmer scribe)
• Lecture 20: TSP Path, and Hirsch Conjecture (RO; Alex Beutel scribe)
• Lecture 21: Interior-point Methods (RO; Deepak Bal scribe)
• Lecture 22: Linear Programming bounds for Codes (RO)
• Lecture 23: Iterative Rounding and Rank Arguments (AG; ?? scribe)

Course Description:

Linear Programs (LPs) and Semidefinite Programs (SDPs) are central tools in the design and analysis of algorithms. In this course, we will study the mathematical foundations behind these convex programs, give algorithms to solve them, and show how LPs and SDPs can be used to solve other algorithmic and math problems of interest. Here are some topics that we plan to cover in the course:

• The structure of LPs and SDPs (and convex programs in general):
  • Linear-algebraic and Geometric views
  • Duality and Farkas Lemma
  • When linear programs have integer solutions
  • Totally unimodular matrices
• Algorithms for solving such mathematical programs:
  • Simplex and other path-following algorithms for LPs
  • The Ellipsoid Algorithm
  • Interior point Algorithms
  • Multiplicative weights methods
  • Algorithms for low-dimensional convex programs
• Algorithmic applications:
  • MSTs, shortest paths, matchings, flows, etc.
  • constraint satisfaction problems
  • Approximation algorithms via solving LPs/SDPs
• Recent breakthroughs:
  • Sub-3/2 approximations for TSP
  • QIP = PSPACE
  • Optimal(?) approximations for every CSP
  • Lower bounds for randomized simplex pivoting Evaluation criteria: The course will have 6--7 homeworks; most problems will involve writing proofs, though some may involve rudimentary programming and working with LP/SDP solvers. Students will be required to act as scribes for the lectures. The breakdown is 75% homeworks, 15% scribing, 10% participation.

Background: We are looking for familiarity with a strong background in algorithms (at least 15-451 or equivalent), as well as significant mathematical maturity. If you do not have any background with LPs it would help to learn a bit about them before the class begins; one recommendation is the book_Understanding and Using Linear Programming_ by Matoušek and Gärtner.

Maintained by Anupam Gupta and Ryan O'Donnell