|
UIUC
|
CS 598: Topics in Combinatorial OptimizationChandra Chekuri
|
|
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 min-max results, and on the polyhedral approach.
Administrative Information
Lectures: Tue, Thu 11.00am-12.15pm
in Siebel Center
Instructor: Chandra Chekuri- 3228
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, 3-Volume book, Springer-Verlag 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, Prentice-Hall, 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
- Non-bipartite matchings, matching polytope and related topics
- Matroids, Polyhedral aspects, Matroid Intersection and Union
- Min-cost Arborescences
- Submodular flows and applications
- Mader's T-path and A-path theorems
- Multiflows, cut-condition, Okamura-Seymour 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:
Sample LaTeX file and algo.sty
- Lecture 1 on 1/19/2010: Introduction, Motivation, Examples.
- Notes by Alina Ene.
- Lecture 2 on 1/21/2010: Background in Polyhedra and Linear Programming: Farkas lemma, Weak and Strong Duality, Complementary Slackness.
- Lecture 3 on 1/26/2010: Background in Polyhedra and Linear Programming: Faces, Decomposition of Polyhedra
- 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: Gomory-Hu 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: Non-bipartite Matching: Tutte-Berge Formula and Maximum Cardinality Matching Algorithm
- Lecture 8 on 2/11/2010: Non-bipartite Matching: Edmonds-Gallai Decomposition, Factor-Critical Graphs
- 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: Primal-Dual Algorithm for Weighted Bipartite Matching
- Notes by Abner Guzman-Rivera
- Schrijver: Combinatorial Optimization, Chapter 17.
- Lecture 11 on 2/23/2010: Edmonds Algorithm for Weighted Non-Bipartite Matching
- Notes by Rajhans Samdani
- Schrijver: Combinatorial Optimization, Chapter 26.
- Lecture 12 on 2/25/2010: Total Dual Integrality and Cunningham-Marsh Formula
- Lecture 13 on 3/2/2010: T-joins 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
- Lecture 16 on 3/11/2010: Uncrossing based proof of Matroid Polytope Integrality, Base Exchange Properties
- 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, 1-11.
- Satoru Iwata: Submodular function minimization, Mathematical Programming Ser B, Vol 112 (1), 45--64, 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 ACM-SIAM 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
- Lecture 25 on 4/27/2010: Submodular Flows and Applications
- Lecture 26 on 4/29/2010: Multiflows and Disjoint Paths, Flow-Cut Gaps
- Notes by Su Lu
- Schrijver: Combinatorial Optimization, Chapter 70 (Vol C).
- Lecture 27 on 5/4/2010: Okamura-Seymour theorem, flow-cut gaps and embeddings
- Notes by Dong Ye
- Schrijver: Combinatorial Optimization, Chapter 74 (Vol C).
Topics for Reading Projects:
- 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 A-path theorem
- Splitting-Off 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