The main paradigm in the course will be the design and analysis of algorithms for combinatorial optimization. We will cover problems that can be solved optimally in polynomial time (matchings, flows, min-cost flows) as well as study problems that are NP-hard, and for which we can develop approximation algorithms. Linear programming techniques will be one of the central themes of the course.
Tentative list of topics:
Basics of linear programming, Duality, Matchings (Hall's Theorem, Tutte's Theorem), Weighted Matching Algorithms, Matroids, Spanning Trees and Arborescences, Network Flow, Approximation Algorithms (Rounding, Primal-Dual Method), Multicommodity Flows and Cut Problems.