
CS 598: Topics in
Combinatorial Optimization

Spring 2010

Course Summary
This course will cover a mix of basic and
advanced topics in combinatorial optimization. Emphasis will be on
structural results and good characterizations via minmax results, and
on the polyhedral approach.
Administrative Information
Lectures: Tue, Thu 11.00am12.15pm
in Siebel Center
1109.
Instructor: Chandra Chekuri 3228 Siebel Center,
2650705, chekuri at cs dot illinois dot edu
Office Hours: By appointment (send email to make one)
Grading Policy: There will be 2 to 3 homeworks and a
reading/project in the second half. Course projects could involve
research on a specific problem or topic, a survey of several papers on
a topic (summarized in a report and/or talk), or an application of
combinatorial optimization to some applied area of interest. I also
expect students to scribe one or two lectures in latex.
Prerequisites: This is a
graduate level class and a reasonable background in algorithms and
discrete mathematics would be needed. Knowledge of basics of
network flow and linear programming would be required though we will
go over the more advanced material.
Study material:
 (Highly) Recommended book: Lex Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, 3Volume book, SpringerVerlag 2003;
also available as a CD.
 Lex Schrijver, Theory of Linear and Integer Programming (Paperback), Wiley, 1998
 J. Lee, A
First Course in Combinatorial Optimization, Cambridge University
Press, 2004.
 W.
Cook, W. Cunningham, W. Pulleyblank and A. Schrijver,
Combinatorial Optimization.

C. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity, PrenticeHall, 1982.

E.L. Lawler, Combinatorial Optimization: Networks and Matroids,
Holt, Rinehart and Winston, 1976.

G. Nemhauser and L. Wolsey, Integer and Combinatorial
Optimization, John Wiley & Sons, 1988.

B. Korte and J. Vygen,
Combinatorial Optimization: Theory and Algorithms,
Algorithms and Combinatorics 21
Springer, Berlin Heidelberg New York, 2006.
 Lecture notes from Michel Goemans:
Advanced topics (2004) and 2009, and first course
 Wiki on open problems in combinatorial optimization from the Egervary Research Group.
List of Topics:
 Introduction, Motivation, and Methodology
 Background on Polyhedra and Linear Programming
 Totally Unimodular Matrices and Applications to Network Flow and Bipartite Matchings
 Nonbipartite matchings, matching polytope and related topics
 Matroids, Polyhedral aspects, Matroid Intersection and Union
 Mincost Arborescences
 Submodular flows and applications
 Mader's Tpath and Apath theorems
 Multiflows, cutcondition, OkamuraSeymour theorem
Note: The above
list is tentative. It may not be possible to cover all of them.
Homework:
Homework 1 given on
02/09/10, due on 02/25/10 in class.
Homework 2 given on
03/02/10, due on 03/18/10 in class.
Homework 3 given on
04/15/10, due on 05/4/10 in class.
Lectures:
For scribing lecture notes.
Sample LaTeX
file and algo.sty
 Lecture 1 on 1/19/2010: Introduction, Motivation, Examples.
 Lecture 2 on 1/21/2010: Background in Polyhedra and Linear Programming: Farkas lemma, Weak and Strong Duality, Complementary Slackness.
 Notes by Sungjin Im.
 Schrijver: Theory of Integer and Linear Programming, Chapters 7,8.
 Schrijver: Combinatorial Optimization, Chapter 5.
 Notes from Michel Goemans class
 Lecture 3 on 1/26/2010: Background in Polyhedra and Linear Programming: Faces, Decomposition of Polyhedra
 Notes by Ben Moseley.
 Schrijver: Theory of Integer and Linear Programming, Chapters 7,8.
 Schrijver: Combinatorial Optimization, Chapter 5.
 Notes from Michel Goemans class
 Lecture 4 on 1/28/2010: Integer Polyhedra, Totally Unimodular Matrices, Examples, Network Matrices
 Notes by GuoJun Qi
 Schrijver: Theory of Integer and Linear Programming, Chapter 19.
 Schrijver: Combinatorial Optimization, Chapter 5.
 Lecture 5 on 2/2/2010: Applications of Integral Polyhedra
via TUM Matrices: Bipartite Matchings, Single Commodity Flows, Interval Graphs
 Notes by Siva Theja Maguluri
 Schrijver: Theory of Integer and Linear Programming, Chapter 19.
 Lecture 6 on 2/4/2010: GomoryHu Trees for Undirected Graphs and Symmetric Submodular Set Functions
 Notes by David Morrison
 Schrijver: Combinatorial Optimization, Chapter 15 Section 4.
 Lecture 7 on 2/9/2010: Nonbipartite Matching: TutteBerge Formula and
Maximum Cardinality Matching Algorithm
 Notes by Matthew Yancey
 Schrijver: Combinatorial Optimization, Chapter 24.
 Notes on maximum matching algorithm from Michel Goemans class
 Lecture 8 on 2/11/2010: Nonbipartite Matching: EdmondsGallai Decomposition, FactorCritical Graphs
 Notes by instructor
 Schrijver: Combinatorial Optimization, Chapter 24.
 Notes
from Michel Goemans class
 Lecture 9 on 2/16/2010: (Perfect) Matching Polytope, Edge Covers
 Notes by Vivek Srikumar.
 Schrijver: Combinatorial Optimization, Chapter 25.
 Lecture 10 on 2/18/2010 by Nitish Korula: PrimalDual Algorithm for Weighted Bipartite Matching
 Notes by Abner GuzmanRivera
 Schrijver: Combinatorial Optimization, Chapter 17.
 Lecture 11 on 2/23/2010: Edmonds Algorithm for Weighted NonBipartite Matching
 Notes by Rajhans Samdani
 Schrijver: Combinatorial Optimization, Chapter 26.
 Lecture 12 on 2/25/2010: Total Dual Integrality and CunninghamMarsh
Formula
 Notes by Bill Kinnersley
 Schrijver: Theory of Integer and Linear Programming, Chapter 22.
 Schrijver: Combinatorial Optimization, Chapter 25.
 Notes (1, 2) from Michel Goemans class
 Lecture 13 on 3/2/2010: Tjoins and applications
 Notes by Ben Raichel
 Cook etal book on Combinatorial Optimization, Chapter 5.
 Schrijver: Combinatorial Optimization, Chapter 29.
 Lecture 14 on 3/4/2010: Introduction to Matroids
 Notes by Vineet Abhishek
 Introductory survey by James Oxley: What is a matroid? A set of slides from an introductory talk by Oxley.
 Schrijver: Combinatorial Optimization, Chapter 39 (Vol B).
 Lecture 15 on 3/9/2010: Maximum Weight Independent Set in a Matroid, Greedy Algorithm, Independence and Base Polytopes
 Notes by Sreeram Kannan
 Schrijver: Combinatorial Optimization, Chapter 40 (Vol B).
 Notes from Michel Goemans class.
 Lecture 16 on 3/11/2010: Uncrossing based proof of Matroid Polytope Integrality, Base Exchange Properties
 Notes by Alina Ene
 Schrijver: Combinatorial Optimization, Chapter 39 (Vol B).
 Notes from Michel Goemans class.
 Lecture 17 on 3/16/2010: Matroid Intersection
 Notes by Jason Sauppe
 Schrijver: Combinatorial Optimization, Chapter 41 (Vol B).
 Lecture 18 on 3/18/2010: Matroid Intersection Polytope
 Notes by Jason Sauppe
 Schrijver: Combinatorial Optimization, Chapter 41 (Vol B).
 Lecture 19 on 4/6/2010: Matroid Union
 Notes by Quan Geng
 Schrijver: Combinatorial Optimization, Chapter 42 (Vol B).
 Lecture 20 on 4/8/2010: Submodular Set Functions, Polymatroids, Ellipsoid based algorithm for Submodular Set Function Minimization
 Notes by Bolin Ding
 Schrijver: Combinatorial Optimization, Chapters 44,45 (Vol B).
 Lectures 21 and 22 on 4/13/2010 and 4/15/2010: Combinatorial Algorithm for
Submodular Set Function Minimization
 Notes
 Schrijver: Combinatorial Optimization, Chapter 45 (Vol B).
 Lisa Fleischer: Recent Progress in Submodular Function Minimization, OPTIMA: Mathematical Programming Society Newsletter , September 2000, no.64, 111.
 Satoru Iwata: Submodular function minimization, Mathematical Programming Ser B, Vol 112 (1), 4564, 2007.
 Alexander
Toshev:
Submodular Function Minimization. Part of a written
preliminary exam at U. Penn, January 2010. See also
his slides.
 S. Iwata and J. Orlin: A Simple Combinatorial Algorithm for Submodular Function Minimization, Proc. of ACMSIAM SODA, 2009.
 Lecture 23 on 4/20/2010: Arborescences and Branchings
 Notes by Jing Gao
 Schrijver: Combinatorial Optimization, Chapter 52 (Vol B).
 Korte and Vygen: Combinatorial Optimization, Chapter 6.
 Lecture 24 on 4/22/2010: Graph Orientations and Directed Cuts, Polymatroid Intersection
 Notes by Zhenhui Li
 Schrijver: Combinatorial Optimization, Chapters 46, 60 (Vol B).
 Notes from Michel Goemans class in 2004
 Lecture 25 on 4/27/2010: Submodular Flows and Applications
 Notes by Peixiang Zhao
 Schrijver: Combinatorial Optimization, Chapters 46, 60 (Vol B).
 Notes from Michel Goemans class in 2004
 Lecture 26 on 4/29/2010: Multiflows and Disjoint Paths, FlowCut Gaps
 Notes by Su Lu
 Schrijver: Combinatorial Optimization, Chapter 70 (Vol C).
 Lecture 27 on 5/4/2010: OkamuraSeymour theorem, flowcut gaps and embeddings
 Notes by Dong Ye
 Schrijver: Combinatorial Optimization, Chapter 74 (Vol C).
Topics for Reading Projects:
Below are a few topics that are potential project material. Consult instructor for additional topics or some thing else that may be of interest to you.
 Alebraic algorithms for matchings and matroid intersection
 Matroid Matching
 Jump Systems
 Path Matchings
 Nowhere zero flows
 Combinatorial algorithms for minimizing submodular functions
 Complexity of submodular partition problems
 Bisubmodular functions and applications
 Algorithmic aspects of Mader's Apath theorem
 SplittingOff Theorems and Applications
 (Recent) Applications of Combinatorial Optimization Techniques
 Submodular functions in machine learning (see Carlos Guestrin's work and surveys)
 Network Coding and Network Information Flow in Wireline and Wirless Networks
 Budgeted Learning
 Iterated Rounding for Network Design and Approximation Algorithms
 Packing Steiner Trees and Forests