47-853 Special Topics in Combinatorial Optimization: Iterative Relaxation and Rounding
Time: Mondays and Wednesdays 3.30-5.30 pm from August 27 - Oct 15 2007.
Place: Room 318, GSIA (old) building
Instructors: R. Ravi and Mohit Singh
Polyhedral methods have been a powerful tool in combinatorial optimization. In this course we will study exact linear programming formulations for a variety of problems which are polynomial time solvable. In particular, we will explore the effectiveness of a new technique based on iterative augmentation in proving some traditional results. We will also examine min-max relations and efficient algorithms for these problems. Towards the end of the class, we will illustrate the original iterative rounding method that inspired these results as well as some applications to approximation algorithms.
Tentative Outline:
1. Linear Programming
2. Bipartite and general matchings
3. Trees and connectivity augmentation
4. Matroid bases, intersection of two matroids
5. Union of matroids and packing trees
6. Submodular flow minimization
7. Graph orientations, Dilworth’s and Lucchesi-Younger theorems
8. Network design and degree constraints
Grades will be based on revising and correcting already prepared preliminary scribe notes, and on one or two problem sets over the course of the class. Solving any open problem posed in class will automatically absolve you from other work!
We require all attendees to register, if only for audit.
