Combinatorial Optimization 2025


References

• Michel Goemans' lecture notes on Combinatorial Optimizarion
  
  
• "Combinatorial Optimization" by Korte and Vygen
  
  
  
  Lecture notes
  
  
  • Jan 21-25:     Lecture 1           Lecture 2
    
    * Matchings in bipartite graphs: König-Egerváry theorem, Hall's theorem, Maximum matching algorithm
    
                                                        Min-cost perfect matching algorithm and Birkhoff-von Neumann theorem
    
    
  • Jan 29-31:     Lectures 3-4
    
    * Matchings in general graphs: Blossoms and Edmonds' algorithm
    
                                                       Tutte's matching theorem and Tutte-Berge formula
    
    
  •     Assignment 1
    
    
    
  • Feb 3-7:     Lectures 5-6
    
    * Edmonds' algorithm and LP basics: Correctness of the algorithm and proof of Tutte-Berge formula
    
                                                                Fourier-Motzkin elimination and Theorem of the Alternatives
    
    
  • Feb 10-14:     Lectures 7-8
    
    * Linear Programming: Theorem of the Alternatives and Farkas' lemma
    
                                          Proof of strong duality theorem, Complementary slackness
    
    
  • Feb 17-21:     Lectures 9-10
    
    * Linear Programming: Another proof of strong duality
    
                                          Faces of polyhedra
    
    
  • Feb 24-28:     holiday           Lecture 11
    
    * Faces of polyhedra: Vertices and facets
    
                                       Polyhedral combinatorics
    
    
  • Mar 3-7:     Lectures 12-13
    
    * Polyhedral combinatorics: A compact extended formulation for the permutahedron
    
                                                 Total unimodularity
    
    
  •     Smallest Compact Formulation for the Permutahedron (paper by Michel Goemans)
    
    
    
  • Mar 10-14:     Lecture 14          holiday
    
    * Matching polytope in general graphs: Edmonds' formulation of the matching polytope
    
    
  •     Assignment 2
    
    
    
  • Mar 24-28:     Lectures 15-16
    
    * Matroids: Definition, Examples, Rank Function
    
                       Greedy Algorithm and The Matroid Polytope
    
    
  • Mar 31-Apr 4:     Lectures 17-18
    
    * Matroids: Different proofs of integrality of the matroid polytope
    
    
  • Apr 7-Apr 11:     Lectures 19-21
    
    * Intersection of two matroids: Examples, Largest common independent set algorithm and its correctness
    
    
  • Apr 14-Apr 18:     Lectures 22-24
    
    * Intersection of two matroids: Matroid intersection polytope and Min-cost arborescence algorithm
    
    
  •     Assignment 3
    
    
    
  • Apr 21-Apr 25:     Lectures 25-26
    
    * Arborescences and spanning trees: Fulkerson's theorem, Packing spanning trees, and Dual matroid