UIUC
Computer Science Department

CS 598: Topics in Combinatorial Optimization

Chandra Chekuri

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 min-max results, and on the polyhedral approach.


Administrative Information

Lectures: Tue, Thu 11.00am-12.15pm in Siebel Center 1109.

Instructor:  Chandra Chekuri- 3228 Siebel Center, 265-0705, 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, 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:

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: 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
    • Notes by Matthew Yancey
    • Schrijver: Combinatorial Optimization, Chapter 24.
    • Notes on maximum matching algorithm from Michel Goemans class
  • Lecture 8 on 2/11/2010: Non-bipartite Matching: Edmonds-Gallai Decomposition, Factor-Critical 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: 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
    • 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: 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
    • 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
  • 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, 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:

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 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