Rasmus Kyng - Tutorial (Part 2): Continuous Methods in Graph Algorithms

Rasmus Kyng delivers Part 2 of the tutorial presentation "Continuous Methods in Graph Algorithms" at the DIMACS Workshop on Modern Techniques in Graph Algorithms held at Rutgers University on June 12, 2023 - June 15, 2023. Abstract: In these talks I will first give an overview of our FOCS'22 paper [*] on solving minimum-cost flow in almost linear time. I will also mention a few follow-up works. Then we'll dig a bit deeper into two components of the algorithm: (1) The L1 interior point method that yields our 'outer loop'. We'll see how it works, and touch on how it might be generalized. This method turns the problem of solving an LP into a sequence of simpler L1-regression-like problems, that we only need to solve very crudely to solve our LP. In the case of flow problems, these L1-regression problems turn into a particularly nice task, known as min-ratio cycle. (2) The Dynamic Spanner construction that we use for edge sparsification inside our data structures. This construction allows us to maintain a sparse subgraph H of a dynamically changing input graph G, with a promise that all distances in G are well-approximated in H. [*] "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time" by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva. The DIMACS Workshop on Modern Techniques in Graph Algorithms presented major advances in the design of efficient graph algorithms that have occurred over the last decade. The goal of this workshop was to bring together researchers from different areas of graph algorithms to share the techniques that have been recently influential in their areas. Topics covered not only fast graph algorithms in the classical setting, but also algorithms in various computational models such as dynamic algorithms, streaming algorithms, and sublinear algorithms.