MS&E 319: Matching Theory, Spring 2022

Location: Shiram 108, Tuesdays and Thursdays 1:30 - 3:00 PM.

Instructor: Amin Saberi
Office Hours: by appointment
Teaching Assistant: Tristan Pollner (
Office Hours: Tuesdays 12:30 - 1:30 PM, Huang 3rd floor. (You can also find me after class if you want to chat about the course.)

Course description:
The theory of matching with its roots in the work of mathematical giants like Euler and Kirchhoff has played a central and catalytic role in combinatorial optimization for decades. More recently, the growth of online marketplaces for allocating advertisements, rides, or other goods and services has led to new interest and progress in this area. The course starts with classic results characterizing matchings in bipartite and general graphs and explores connections with algebraic graph theory and discrete probability. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride sharing.

Reading material:
Lecture notes or links to papers & surveys will be available on the class webpage. The following textbook is recommended:
Course load and grading:
Two homework assignments (25% each) and research project (50%).


You can find last year's course homepage here.