- [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
- 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