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.