ISYE 7686: Advanced Combinatorial Optimization
- Instructor: Mohit Singh
- Office: Groseclose Building
- Contact: mohitsinghr@gmail.com
- Lecture: TU,TH 1:35PM-2:55PM
- Office Hours: TU 3:00PM-4:00PM
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:
- Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver, Springer 2003.
Recommended Reading:
Grading:
- 25% Homeworks, 25% Mid-term and 50% Final Exam.
Lectures and Readings:
Lecture 1 (1/10): Matchings and Vertex Cover in Bipartite Graphs (Chapter 16 Schrijver, Section 16.1-16.6).
Lecture 2 (1/12): Weighted Matchings in Bipartite Graphs (Chapter 17 Schrijver, Section 17.1-17.2). Background: Shortest Paths (Chapter 6 (6.1-6.3),7 (7.1-7.2),8(8.1-8.4) Schrijver).
Lecture 3 (1/17): Max Flow - Min cut (Chapter 10 Schrijver. Section 10.1-10.6).
Lecture 4 (1/19): Circulations (Chapter 11 Schrijver).
Lecture 5 (1/24): Min Cost Flows (Chapter 12 Schrijver).
Lecture 6 (1/26): Totally Unimodular Matrices (Chapter 5.16 Schrijver)
Lecture 7 (1/31): Network Matrices, Tutte-Berge Formula (Chapter 24.1, Schrijver).
Lecture 8 (2/2): Unweighted Matching (Chapter 24.2 Edmonds Blossom Algorithm)
Lecture 9 (2/7): Perfect Matching Polytope (Chapter 25, Schirjver)
Lecture 10 (2/9): Total Dual Integrality, Matching Polytope (Chapter 5.17, Chapter 25 Schrijver)
Lecture 11 (2/14): Edmonds Algorithm for weighted matching (Chapter 26, Schrijver).
Lecture 12 (2/16): Edmonds Algorithm for weighted matching (Chapter 26, Schrijver).
Lecture 13 (2/21): Matroid Definitions, Examples (Chapter 39).
Lecture 14 (2/23): Greedy Algorithm for matroids (Chapter 40)
Lecture 15 (2/28): Matroid Polytope, TDI (Chapter 40).
Lecture 16 (3/2): Mid-Term
Lecture 17 (3/7): Matroid Intersection Examples (Chapter 41, Schrijver)
Lecture 18 (3/9): Matroid Intersection Algorithm (Chapter 41, Schrijver)
Lecture 19 (3/13): Matroid Intersection Polytope (Chapter 41, Schrijver)
Lecture 20 (3/15): Matroid Union(Chapter 42, Schrijver)
Lecture 21 (3/28): Submodular Function Examples, Polymatroids Greedy Algorithm(Chapter 44)
Lecture 22 (3/30): Submodular function minimization, Lovasz Extension (Chapter 45.1 Schrijver)
Lecture 23 (4/4): Polymatroid Intersection, Sandwich Theorem (Chapter 46, Schrijver)
Lecture 24 (4/6): Graph Orientation and Lucchesi-Younger Theorem (Chapter 55.1 55.2, 61.2,61.3).
Lecture 25 (4/11): General Submodularity, Submodular Flows (Chapter 60.1,60.2, Schrijver)
Lecture 26 (4/13): Spanning Tree and Arborescence Polytope (Chapter 50,52 Schrijver)
Lecture 27 (4/18): Packing Arborescences (Chapter 53, Schrijver)
Lecture 28 (4/20): Perfect Graphs
Lecture 29 (4/25): Review