Combinatorial Optimization
The course aims to cover basic techniques in combinatorial optimization. Specifically, it will include basics of
linear programs and polytopes, their integrality, matchings and their applications, matroids and optimization etc.
References
- [C] Notes from a course by Prof. Chandra Chekuri
- [PS] C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity
- [S] Lex Schrijver: Combinatorial Optimization: Polyhedra and Efficiency
- [MG] Understanding and Using Linear Programming: Jiří Matoušek and
Bernd Gärtner (Springer)
We may use lecture notes available online. I will specify them as and when necessary
-
Jan 3: Introduction: NP optimization problems, Example: network flows, bipartite matching (Chapter 1 from [C])
- Jan 5: Bipartite matching: augmenting path algorithm, LP formulation (Ref: Section 1.1 of these notes)
- Jan 10: Non-bipartite matchings: Edmond's algorithm, correctness, Tutte-Berge formula (Ref and Chapter 2 of [C])
- Jan 12: Basics of LP and polyhedra (Chapter 3 from [C], and these notes)
- Jan 17: Integrality of bipartite matching polytope (Section 2 of these notes), introduction to LP duality (Sections 6.1,6.2 of [MG]), dual of the bipartite matching polytope
- Jan 19: König's theorem via maximum bipartite matching algorithm, primal-dual algorithm for min-cost perfect matching in bipartite graphs (Ref)
- Jan 24: Primal-dual algorithm continued, two definitions of a face of a polytope and their equivalence, dimension of a face, vertices of a polytope as the intersection of n linearly independent constraints (Ref)
- Jan 31: Total unimodularity: definition, examples: bipartite matching, network flows (Chapter 5 of [C])
- Feb 2: Integrality of general matching polytope (Theorem 8.1 of [C])
- Feb 7: Farka's lemma proof by Fourier-Motzkin elimination, strong duality using Farka's lemma (Chapter 6 of [MG])
- Feb 9: Strong vs weak polynomial-time, introduction to ellipsoid algorithm (Ref: Section 7.1 of [MG], these notes)
- Feb 14: Details of ellipsoid algorithm (Ref: same as above)
- Feb 16: Application of ellipsoid algorithm for solving LP with exponentially many constraints and polynomial-time separation oracle: Non-bipartite matching (Reference, also see Section 6.5 of this)
- Feb 21: Edmonds-Gallai decomposition (Chapter 9 of [C])
- Feb 23: Edmonds-Gallai decomposition continued, introduction to primal-dual algorithm for minimum cost perfect matchings
- Mar 6: Primal-dual algorithm for minimum cost perfect matching in general graphs (Ref: Chapter 10 of [C], these notes)
- Mar 8: Introduction to matroids: definition, examples, linear representation of matroids, uniform, free, graphic, partition, matching matroids, regular matroids, circuits and their uniqueness (Ref: Chapter 13 of [C] and notes)
- Mar 15: Greedy algorithm for maximum weight base in a matroid (Ref: Same as above)
- Mar 20: Rank and span, matroid intersection examples (notes)
- Mar 22: Strong base exchange property, exchange graph of a matroid and its properties (Same notes as above)
- Mar 27: Matroid intersection continued
- Apr 3: Matroid intersection completion
- Apr 5: Matroid union, application to k-disjoint spanning trees
Presentations (Click the link for notes)
- Apr 10: A simple combinatorial algorithm for submodular function minimization Rishav Gupta, Aditya Kannan
- Apr 12: Jump systems Ankit Gayen, linear matroid intersection via determinants Srijan Chakraborty
- Apr 17: Integrality of stable matching polytope Avik Shakhari, distributed approximation algorithm for bipartite vertex cover Soumyadeep Paul
- Apr 18: EFX allocations of indivisible chores: a matching based approach Deepro Sarkar
- Apr 22: Matching is as easy as matrix inversion Suneet Patil and Aritra Majumder
- Apr 23: Fair matchings Shruti Patil and Saptarshi Sadhukhan
- Apr 24: Matching polytope has exponential extension complexity Rohan Goyal and Aditi Muthkhod