Continuous Methods in Discrete Optimization

Continuous approaches have been at the heart of discrete optimization since the advent of linear programming. This selected topics course will focus on some classical and some more recent techniques, where continuous relaxations play an essential role in solving a discrete optimization problem, or when continuous algorithms provide highly efficient solution approaches.

Tentative list of topics:

• Semidefinite programming, with applications to max cut and graph colouring
• Multiplicative weights updates, with applications to online optimization, and solving LPs and semidefinite programs
• Laplacians, graph partitioning and sparsification. Laplacian solvers for maximum flows
• Interior point methods, with applications to fast flow algorithms

This course will be in English and based on various sources. Additional lecture notes will be provided for some of the topics. Sources will include the following books that are available online:

• Monique Laurent, Frank Vallentin. Semidefinite Optimization, Lecture notes (2012)
• Sanjeev Arora, Elad Hazan, Satyen Kale. The Multiplicative Weights Update Method: A Meta Algorithm and its Applications. Theory of Computing, Vol 8, pp. 121-164 (2012)
• Nisheeth Vishnoi. Algorithms for Convex Optimization, Cambridge University Press (2021)
• Nisheeth Vishnoi. Lx=b. Foundations and Trends in Theoretical Computer Science (2013)

Prerequisites:	Linear and Integer Optimization (V3C1/F4C1), in particular, basic knowledge on linear progamming and duality and network flows, e.g. Chapters 1-9 of the Korte-Vygen textbook
Class Hours:	Fridays 10:15-12:00
Room:	Seminarraum, Lennéstr. 2
Exams:	Oral exams, to be scheduled individually.