[theory-seminar] A course on Matching Theory

[Amin Saberi]

Dear friends,

I am teaching the following course in the Spring quarter:

Amin



MS&E 319: Matching Theory
Amin Saberi
T Th 01:30p-03:00p
Shriram Center for BioCheme, Rm 108

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.

Topics include:

Matching, determinant, and Pfaffian
Matching and polynomial identity testing
Isolating lemma and matrix inversion, matching in RNC

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
The Gallai-Edmonds decomposition, Berge-Tutte formula, and applications in Nash bargaining

The stable marriage problem
Gale-Shapley theorem, incentive and fairness issues
LP characterization, counting stable matchings

Matching in dynamic environments
Online matching under various arrival models
Applications in ride-sharing and online advertising

Computation of matching
Combinatorial vs continuous algorithms, near-linear time algorithms
Matchings in sub-linear time, streaming computational models
Sparsifiers and stochastic matching

Counting matchings
The Van der Waerden conjecture, Bregman-Minc’s inequality
Deterministic approximations, counting matchings in planar graphs
Markov chain Monte Carlo algorithms, sequential importance sampling
The Ising model, applications, and basic properties

The matching polynomial and its roots
Heilman-Lieb theorem, the maximum root of the matching polynomial
treelike walks, 2-lifts, and Bilu-Linial conjecture

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220323/8264eb02/attachment.html>