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.)
Scribe notes:
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