## 15-859(E): Linear and Semidefinite Programming (Advanced Algorithms) Fall 2011

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.)

How to 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