Instructor: Swati Gupta
Office: Groseclose Building 437
Lecture: Tu, Th 3:00-4:15 PM, ISyE Main 126
Office Hours: Tu 4:15-5:15 PM.

Description: We will study classical as well as recent results in combinatorial optimization including matchings, network flows, matroids and submodular function optimization. In addition to algorithmic questions, emphasis will be given to polyhedral characterization and combinatorial min-max relations.

Textbook: Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver, Springer 2003.

Recommended Reading:

Grading: Homeworks (40%), Midterm (25%), Final (35%). There will be 4-5 problem sets throughout the semester. 


Background (self-reading): Chapters 1,2 from Alexander Schrijver’s course notes.

Lecture 1: Stable sets, Vertex and Edge Covers, Gallai’s Theorem, K\:{o}nig’s Theorem, Bipartite Matching, Maximum Cardinality Bipartite Matching (Sections 3.1-3.4 from Alexander Schrijver’s course notes, 16.1-16.5 from course book). 

Lecture 2: Maximum Weight Matching, Bipartite Matching Polytope. Chapter 3 from Schrijver’s course notes, Chapter 17.1-17.3, 18.1 from book, Lecture 1 from Goeman’s course notes.  

Tentative topics Lecture 3 onwards: Max flow min cut, Min cost circulation, Iterative rounding, Total Unimodularity, Matchings in General Graphs, Perfect Matching Polytope, Total Dual Integrality and Matching Polytope, T-joins, Packing T-cuts, T-join Polytope, Gomory-Hu trees and T-cuts, Spanning tree polytope, Matroid Polytope, Total Dual Integrality, Matroid Intersection, Matroid Union, Submodular Functions, Polymatroids Greedy Algorithm, Submodular function minimization, Lov\'{a}sz Extension, Polymatroid Intersection, Graph Orientation, General Submodularity, Submodular Flows, Perfect Graphs