ISYE 7686: Advanced Combinatorial Optimization

Instructor: Mohit Singh
Office: Groseclose Building 410
Contact: mohitsinghr@gmail.com
Lecture: TU,TH 3:00PM-4:15PM, ISYE Annex 228
Office Hours: TU 4:15PM-5:15PM

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

Recommended Reading:

Grading:

Homeworks.

Lectures and Readings:

  • Background: Chapter 1 and Chapter 2 from Course notes by Schrijver.
  • Lecture 1: Bipartite Matching. Chapter 3 from course notes by Schrijver. Chapter 16.1-16.3, 16.5 from book.
  • Lecture 2: Maximum weight matching. Bipartite matching polytope. Chapter 3 from course notes by Schrijver. Chapter 17.1-17.3, 18.1 from book.
  • Lecture 3: Maximum Flow and Minimum Cut, Hoffman's Circulation Theorem. Chapter 4 from course notes by Schrijver. Chapter 10.1-10.5, Chapter 11.1-11.3 from book.
  • Lecture 4: Minimum Cost circulation and flows. Chapter 4 from course notes by Schrijver. Chapter 12.1-12.3 from book.
  • Lecture 5: Iterative Rounding and Integrality of bipartite matching. Chapter 1 and 2 from Iterative methods in Combinatorial Optimization.
  • Lecture 6: Total Unimodularity. Chapter 8 from course notes by Schrijver. Chapter 5.14-5.16 from book.
  • Lecture 7: Matchings in General Graphs. Chapter 4 from course notes by Schrijver. Chapter 24.1-24.3 from book.
  • Lecture 9: Perfect Matching Polytope. Chapter 5 from course notes by Schrijver. Chapter 25.1-25.2 from book.
  • Lecture 12: Total Dual Integrality and Matching Polytope. Chapter 5.17 from book. Chapter 25.3 from book.
  • Lecture 10: Algorithm for Weighted Matching. Chapter 5 from course notes by Schrijver. Chapter 26.1-26.2 from book.
  • Lecture 11: Algorithm for Weighted Matching. Chapter 5 from course notes by Schrijver. Chapter 26.1-26.2 from book.
  • Lecture 13: T-join, Packing T-cuts, T-join Polytope. Chapter 29.1-29.6 from book.
  • Lecture 14: Gomory-Hu trees and T-cuts. Chapter 15.4 from book. Chapter 29.9-29.10 from book.
  • Lecture 15: Spanning tree polytope. Chapter 5 from course notes by Schrijver. Chapter 50.1-50.4 from book.
  • Lecture 15: Matroid Polytope, TDI (Chapter 40).
  • Lecture 16: Mid-Term
  • Lecture 17: Matroid Intersection Examples (Chapter 41, Schrijver)
  • Lecture 18: Matroid Intersection Algorithm (Chapter 41, Schrijver)
  • Lecture 19: Matroid Intersection Polytope (Chapter 41, Schrijver)
  • Lecture 20: Matroid Union(Chapter 42, Schrijver)
  • Lecture 21: Submodular Function Examples, Polymatroids Greedy Algorithm(Chapter 44)
  • Lecture 22: Submodular function minimization, Lovasz Extension (Chapter 45.1 Schrijver)
  • Lecture 23: Polymatroid Intersection, Sandwich Theorem (Chapter 46, Schrijver)
  • Lecture 24: Graph Orientation and Lucchesi-Younger Theorem (Chapter 55.1 55.2, 61.2,61.3).
  • Lecture 25: General Submodularity, Submodular Flows (Chapter 60.1,60.2, Schrijver)
  • Lecture 26: Perfect Graphs (Chapter 53, Schrijver)
  • Lecture 27: Max Cut
  • Lecture 28: Review