EdusalsaDiscover Your Stanford

MS&E 319

Approximation Algorithms

  • Not Offered

3 units

Letter or Credit/No Credit

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.

Course Prequisites

Sign Up

To save MS&E 319 to your course bucketlist

Already Have An Account? Log In