Introduction to Modern Combinatorial Optimization

2025 Winter Lecture Series

January 13 - 17, The Center for Algorithm and Optimization (CALOP) at POSTECH

Instructor: Dabeen Lee (Department of Industrial and Systems Engineering, KAIST)
Email: dabeenl [at] kaist [dot] ac [dot] kr

Text: No required text, but the following materials are helpful.

Recommended textbooks and lecture notes

• On the History of Combinatorial Optimization (Till 1960) by Alexander Schrijver.
• Introduction to Graph Theory by Douglas B. West.
• Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver.
• Integer Programming by Michele Conforti, Gerald Cornuejols, and Giacomo Zambelli.
• Submodular Function Maximization by Andreas Krause and Daniel Golovin.

Syllabus (pdf)

One of the early developments in combinatorial optimization dates back to 1784 when G. Monge studied the assignment problem in the context of transporting molecules. Later, in the early 20th century, pioneering works on bipartite matching and linear programming came to light. Since then, innovations in combinatorial optimization have revolutionized all areas of operations research and computer science. To date, algorithms and techniques inspired by combinatorial optimization have played a central role in scientific fields including machine learning, artificial intelligence, market design economics, protein structure prediction, and drug design. Motivated by this, this course aims to equip students with an in-depth understanding of comprehensive aspects of combinatorial optimization. We will cover a wide range of topics, from classic results to modern approaches, about fundamental theory and practical algorithms.

Lecture notes

1. Lecture 1: introduction to bipartite matching: graph theory basics and the greedy algorithm (lecture note, slides)
2. Lecture 2: the augmenting path algorithm for bipartite matching based on the alternating tree procedure (lecture note, slides)
3. Lecture 3: linear programming for bipartite matching (lecture note, slides)
4. Lecture 4: Hall's marriage theorem for perfect bipartite matching, König's theorem (lecture note, slides)
5. Lecture 5: the Hungarian algorithm for maximum weight bipartite matching, application of bipartite matching: matching markets (lecture note, slides)
6. Lecture 6: extensions of bipartite matching: stable matching and online bipartite matching (lecture note, slides)
7. Lecture 7: nonbipartite matching, polyhedral theory basics (lecture note, slides)
8. Lecture 8: the matching polytope and separation (lecture note, slides)
9. Lecture 9: submodular function minimization, chance-constrained programming (lecture note, slides)
10. Lecture 10: discrete and continuous submodular function maximization (lecture note, slides)
11. Lecture 11: black box optimization (lecture note, slides)
12. Lecture 12: recent progress on reinforcement learning with function approximation (slides)