MS&E 319: Matching Theory, Spring 2019
Instructor: Amin Saberi
TA: Ali Shameli
Location: Lane History Corner 200-219, Mondays 10:30-13:20
Office Hours: Huang B016, Mondays 16:00-17:00
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 link to papers & surveys will be available on the class webpage. The following textbook is recommended:
- L. Lovasz, M.D. Plummer, Matching Theory, 1986.
Grading:
There will be 3 homework assignments of 20% each and a research project of 50%.
Lectures:
- 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 notes (I and II), 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.
- Week 7: The matching polynomial and its roots
- Matching polynomial, its roots and properties: See the class notes and also these lecture notes by Daniel Spielman.
- Ramanujan graphs, Bilu-Linial conjecture, and interlacing families: Look at this paper by Marcus, Spielman, and Srivastava.
- Week 8: The stable marriage problem
- Deferred acceptance procedure and the existence of stable marriages: See this classic paper by Gayle and Shapley.
- The stable matching problem in a probabilistic setting and its incentive/fairness issues: Look at this paper by Immorlica and Mahdian and their followup by Ashlagi, Kanoria, and Leshno.
- See the notes.
- Week 9: Counting matchings
- Permanent of a matrix and connection to matchings
- Self reducibility and equivalence of counting and sampling
- Approximating the permanent using Markov Chain Monte Carlo method: See this by Jerrum and Sinclair.
- Van der Waerden conjecture and deterministic approximations of the permanent: See this paper by Linial, Samorodnitsky, and Wigderson and this paper by Gurvits.
Sample file for scribes
Homework: