Instructor: Adrian Vladu
Time and place: Thursdays, 12:45-3:45 pm, Sophie Germain building, room 1002
Prerequisites
Linear algebra, basic algorithms, basic notions in probability. The class will move fairly quickly, so some mathematical maturity is required.
Course description
This course will cover a series of ideas and techniques at the boundary between combinatorial and continuous optimization. In particular we will focus on graph algorithms, interpreted through the prism of continuous methods.
The final grade will be based on a final exam and a research-oriented project, chosen with the help of the instructor.
Light homework will be assigned. While this will not count towards your final grade, solving it will help you guarantee a good grade on the final exam (which will take place on December 1, 12:45pm, room 1002).
Schedule
15/09 | Basics of optimization. Learning with experts. Algorithmic applications (Plotkin-Shmoys-Tardos, oblivious routings) | Hw1 on Overleaf |
22/09 | J-trees, dynamic minimum spanning tree. Fast graph cut approximators using J-trees. | |
29/09 | Iterative methods for solving linear systems. Preconditioning. | |
06/10 | No lecture | |
13/10 | Laplacian matrices and linear systems. Equivalence to electrical flows. | Hw2 on Overleaf |
20/10 | Matrix Chernoff and spectral sparsification. Augmented tree preconditioners. | Hw3 on Overleaf |
27/10 | Algorithmic graph theory using electrical flows. Interior point methods. | Hw3 extra exercise on Overleaf |
03/11 | Interior point methods (continued). | |
10/11 | Wrap-up, open problems. | |
01/12 | In-class exam. |
Projects
The final project can take several forms: