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

Problem set


We may use lecture notes available online. I will specify them as and when necessary

Lectures

  1. Jan 3: Introduction: NP optimization problems, Example: network flows, bipartite matching (Chapter 1 from [C])
  2. Jan 5: Bipartite matching: augmenting path algorithm, LP formulation (Ref: Section 1.1 of these notes)
  3. Jan 10: Non-bipartite matchings: Edmond's algorithm, correctness, Tutte-Berge formula (Ref and Chapter 2 of [C])
  4. Jan 12: Basics of LP and polyhedra (Chapter 3 from [C], and these notes)
  5. 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
  6. Jan 19: König's theorem via maximum bipartite matching algorithm, primal-dual algorithm for min-cost perfect matching in bipartite graphs (Ref)
  7. 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)
  8. Jan 31: Total unimodularity: definition, examples: bipartite matching, network flows (Chapter 5 of [C])
  9. Feb 2: Integrality of general matching polytope (Theorem 8.1 of [C])
  10. Feb 7: Farka's lemma proof by Fourier-Motzkin elimination, strong duality using Farka's lemma (Chapter 6 of [MG])
  11. Feb 9: Strong vs weak polynomial-time, introduction to ellipsoid algorithm (Ref: Section 7.1 of [MG], these notes)
  12. Feb 14: Details of ellipsoid algorithm (Ref: same as above)
  13. 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)
  14. Feb 21: Edmonds-Gallai decomposition (Chapter 9 of [C])
  15. Feb 23: Edmonds-Gallai decomposition continued, introduction to primal-dual algorithm for minimum cost perfect matchings
  16. Mar 6: Primal-dual algorithm for minimum cost perfect matching in general graphs (Ref: Chapter 10 of [C], these notes)
  17. 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)
  18. Mar 15: Greedy algorithm for maximum weight base in a matroid (Ref: Same as above)
  19. Mar 20: Rank and span, matroid intersection examples (notes)
  20. Mar 22: Strong base exchange property, exchange graph of a matroid and its properties (Same notes as above)
  21. Mar 27: Matroid intersection continued
  22. Apr 3: Matroid intersection completion
  23. Apr 5: Matroid union, application to k-disjoint spanning trees

  24. Presentations (Clique the link for notes)


  25. Apr 10: A simple combinatorial algorithm for submodular function minimization Rishav Gupta, Aditya Kannan
  26. Apr 12: Jump systems Ankit Gayen, linear matroid intersection via determinants Srijan Chakraborty