Graphs, Linear Algebra, and Continuous Optimization
Lecturer:
Aleksander Mądry
(MIT, USA).
About the lecturer | Course Summary | Slides: 1 2 3 | Assignment
About the lecturer:
Aleksander Mądry is an assistant professor in the MIT EECS Department.
His research centers on algorithmic graph theory and understanding
uncertainty in the context of optimization.
Aleksander received his PhD from MIT in 2011 and, prior to joining the MIT faculty, he spent a year as a postdoctoral researcher at Microsoft Research New England and then almost three years on the faculty of EPFL. His work was recognized with a variety of awards, including the ACM Doctoral Dissertation Award Honorable Mention, the George M. Sprowls Doctoral Dissertation Award, and a number of best paper awards at FOCS/SODA/STOC conferences.
Course summary: Graphs are ubiquitous in all aspects of computer science. This motivates a constant search for algorithmic tools that are capable of analyzing and computing on graphs in more efficient manner.
The goal of this course is to outline a new approach to designing fast graph algorithms. Broadly speaking, this approach relies on combining traditional combinatorial techniques with tools and methods borrowed from linear algebra and continuous optimization.
Our main focus will be on the maximum flow problem and the, closely related, bipartite matching problem, which are among the most fundamental tasks in algorithmic graph theory. More specifically, the lecture will touch on the following topics:
- Traditional approaches to the maximum flow problem and the (maximum cardinality) bipartite matching problem;
- The notion of electrical flows and fast Laplacian system solvers;
- Elements of spectral graph theory;
- Fast approximation of maximum flows in undirected graphs using electrical flows;
- Interior-point methods and fast algorithms for the exact maximum flow problem in directed graphs.
Assignment: You can find the problem set here. Please send the solutions to Bartek Klin (klin@you-know-what) by Wednesday, May 13.