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
219. (You can also find me anytime at Huang 212W 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 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
(50%).
Lectures:
- Week 1: Matching, determinant, and Pfaffian
- Matching and polynomial identity testing.
- Isolating lemma and matrix inversion, matching in RNC.
- See the notes for lectures 1 and 2, and the MVV paper.
- Week 2: Combinatorial and polyhedral characterizations
- Konig's theorem and polyhedral formulation of perfect matching.
- Tutte's theorem, Edmond's LP and the Blossom algorithm.
- The assignment problem and its dual, primal-dual and auction algorithms.
- See the notes on the according lectures.
- See the lecture notes by Michel Goemans on bipartite and non-bipartite matching, and Edmonds's Paths, Trees, and Flowers paper.
- Week 3 & 4: 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 follow up by Jaillet and Lu. Also see Section 3.3 of the booklet.
- For applications to online advertising, see the MSVV paper and the follow up by Buchbinder, Jain and Naor using primal-dula analysis. Also check this technical note by Niazadeh and Kleinberg for a unified approach using randomized dual fitting.
- See also the scribed notes on the analysis of KVV and notes for the primal-dual analysis of MSVV.
- Week 5 & 6: Matroids and submodular optimization
- Definition and examples matroids, the greedy algorithm for finding the base with the maximum weight.
- See the notes on matroid intersection and applications, the matroid intersection theorem.
- See the notes for continuous extensions explaining Lovasz extension and Multilinear extension.
- Submodular functions, unconstrained submodular maximization (notes), greedy algorithm. Check this paper by Feldman, Naor and Schwartz for continuous extensions and also the
handbook for proofs in submodular welfare maximization.
- See the excellent notes by Vondrak.
- Week 7 & 8:
- See the notes on Van Der Waerden Inequality, Bregman-Minc Inequality and Sequential Importance Sampling.
- See the notes on Gurvits Theorem and Nash Welfare.
- To see properties of permanent of PSD matrices and approximation algorithms to compute it, check this notes.
Sample file for scribes
Homework:
You can find last year course homepage in here.