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:

  1. Making a theoretical contribution, such as solving an open problem, or bringing a new perspective on an existing theoretical question.
  2. Writing a short survey, based on a few papers, that covers a topic that is related to the course material.
  3. Implementing one of the algorithms presented in the class and evaluating its performance in practical scenarios.