Continuous Methods in Combinatorial Optimization 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: Making a theoretical contribution, such as solving an open problem, or bringing a new perspective on an existing theoretical question. Writing a short survey, based on a few papers, that covers a topic that is related to the course material. Implementing one of the algorithms presented in the class and evaluating its performance in practical scenarios.