Semester: Spring 2020
Instructor: Swati Gupta
Office: Groseclose Building 437
Contact: swatig@gatech.edu
Lecture: Tu, Th 4:30-5:45 PM, ISyE Main 126
Office Hours: By appointment
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:
- A course in Combinatorial Optimization, Course Notes by Alexander Schrijver.
- Topics in Combinatorial Optimization, Course Notes by Michel Goemans, MIT.
- Topics in Combinatorial Optimization, Course Notes by Chandra Chekuri, UIUC.
- Iterative methods in Combinatorial Optimization, Lap Chi Lau, R. Ravi and Mohit Singh, Cambridge University Press, 2011.
Grading: Homeworks (40%), Midterm (25%), Final (35%).
Tentative Topics: Non-bipartite Matchings, Edmonds’ Blossom Algorithm, Edmonds-Gallai Decomposition and alternate proof using the Tutte-Berge theorem, Iterative rounding, Min-cost flows and circulations, Nowhere Zero Flows, Total Unimodularity, 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
Comments are closed.