MS&E319 - Approximation Algorithms

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, permanent, Pfaffian and counting and sampling matchings. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride sharing. May be repeated for credit. Prerequisite: 212, CS 261, or equivalent.
Career
Graduate
Grading Basis
ROP - Letter or Credit/No Credit
Min
3
Max
3
Course Repeatable for Degree Credit?
Yes
Total Units Allowed for Degree Credit
999

Course Component
Lecture
Enrollment Optional?
No