Fast Algorithms

How can we solve combinatorial optimization problems faster? This sixth edition of the Cargese workshop will focus on techniques that emerged in the context of this goal, as well as on the underlying ideas, coming mostly from an interplay of continuous and combinatorial worlds. At the heart of the recent breakthroughs lie a few central meta-algorithms such as gradient descent, multiplicative weight update (MWU) or Newton’s methods. We will learn about these tools and how to build upon them to design the fastest known algorithms for classic optimization tasks such as bipartite matching and maximum flow problems. We will also cover a number of other primitives that ended up being critical in design of fast algorithms. Examples include various notions of sparsification, and the electrical flow computations.