Instructor: Swati Gupta
Office: Groseclose Building 437
Contact: swatig@gatech.edu
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. 

Lectures:

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

Lecture 1 (Jan 8): 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 (Jan 10): 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 Goemans’ course notes. 

Lecture 3 (Jan 15): Maximum weight matching in general graphs, Edmonds’ Blossom Algorithm

Lecture 4 (Jan 17), 5 (Jan 22): Edmonds-Gallai Decomposition and alternate proof using the Tutte-Berge theorem

Lecture 6 (Jan 24): Min cost flows and circulations (Chapter 4 from Schrijver’s course notes, Chapter 10.1-10.5, Chapter 11.1-11.3 from book.)

January 29: no class due to weather

January 31: no class

Lecture 7 (Feb 5): Guest Lecture by Mohit Singh. Iterative rounding for integrality of the bipartite matching polytope. Chapter 1,2 from Iterative methods in Combinatorial Optimization. 

Lecture 8 (Feb 7): Min cost flows and circulations (Chapter 4 from course notes by Schrijver. Chapter 12.1-12.3 from book.)

Lecture 9 (Feb 8, 4-5:15 PM, Main 126):  Nowhere Zero Flows (Lecture 4 from Goemans’ course notes, Chapter 28 from Schrijver’s book. )

Lecture 10 (Feb 12): 

Tentative topics lecture 10 onwards: Total Unimodularity, 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