MS&E 319: Matching Theory, Fall 2019
Location: Lane History Corner 200-107, Tuesdays and Thursdays 10:30-11:50.
Instructor: Amin Saberi
Office Hours: by appointment
Teaching Assistant: Mobin Yahyazadeh (yahyazad@stanford)
Office Hours: Tuesdays 5-6 pm, Huang 138 this week (10/15), Huang
219 every other week
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.
Lecture notes or link to papers & surveys will be available on the class webpage. The following textbook is recommended:
Course load and grading:
Two homework assignments (15% each), scribing notes for one lecture (20%), and research project and presentation
Sample file for scribes
- Week 1: Matching, determinant, and Pfaffian
- Matching and polynomial identity testing
- Isolating lemma and matrix inversion, matching in RNC
- See the notes and the MVV paper.
- Week 2 & 3: Combinatorial and polyhedral characterizations
- The assignment problem and its dual, primal-dual and auction algorithms
- Tutte's theorem, Edmond's LP and the Blossom algorithm
- See the lecture notes by Michel Goemans on bipartite and non-bipartite matching, and Edmonds's Paths, Trees, and Flowers paper.
- Week 4 & 5 & 6: Online Matching
- Online bipartite matching: See the KVV paper and this booklet by Aranyak Mehta where you can find the correct analysis of the RANKING algorithm (Section 3.1.2). Also see this for analysis of the RANKING algorithm using the primal-dual approach.
- Online stochastic matching: See the online stochastic matching paper by Manshadi, Oveis Gharan, and Saberi and their followup by Jaillet and Lu. Also see Section 3.3 of the booklet.
- Dynamic matching markets (timing and market thickness): See this paper by Akbarpour, Li, and Oveis Gharan and their followup by Liu, Wan, and Yang.
- AdWords: See the MSVV paper and their followup by Buchbinder, Jain, and Naor which derives their result using a clean primal-dual approach. Also check this technical note by Niazadeh and Kleinberg, where they rederive the MSVV result as well as some other known results in online matching using the unified approach of randomized dual fitting.
- Look here for some open problems discussed in class.
You can find last year course homepage in here.