Dynamic algorithms and optimization (Part 1) by Richard Peng

STOC'22 Workshop
Dynamic Algorithms: Recent Advances and Applications

Abstract:
Many recent developments in efficient algorithms are based on optimization routines. Such routines converge to optimum solutions via sequences of gradually changing subproblems, and have direct connections with dynamic algorithms. The first half of this talk will overview first- and second- order optimization algorithms, and their connections with (implicitly) maintaining solutions of dynamically changing linear systems. The second half of this talk will discuss the design of dynamic graph data structures tailored toward combinatorial optimization problems, including partitioning, sparsification, and vertex elimination algorithms.