Theory Seminar: Recent Advances in Fast Algorithm Design for Structured Linear Programming and Its Implications in Combinatorial Optimization

Abstract: An extremely fruitful line of algorithms research over the past decade has been the application of interior point methods alongside data structure design to classical problems in combinatorial optimization. Most prominently, this approach led to an almost-linear time algorithm for the max-flow problem [CKL+, FOCS23].

In this talk, we consider linear programs minimizing a linear objective in the variables x, subjected to Ax = b, x >= 0, where the constraint matrix A has suitable structural properties. We present a general framework for solving these structured linear programs that ties together interior point methods and tools across theoretical computer science including graph decomposition, sampling,
parameterized complexity, and numerical linear algebra. Our framework in turn yields the fastest-known algorithms for min-cost flow and k-commodity flow on planar graphs, and for min-cost flow and general linear programs on graphs with bounded treewidth.

Based on joint work with Yu Gao, Gramoz Goranci, Yin Tat Lee, Lawrence Li, Richard Peng, Sushant Sachdeva, and Guanghao Ye.

Bio: Sally Dong is a PhD candidate in theoretical computer science at the University of Washington advised by Yin Tat Lee and Thomas Rothvoss. Her research currently focuses on the design and analysis of provably-fast algorithms for foundational problems in combinatorial optimization, such as the max flow problem and linear programming. She completed her bachelor's degree at the University of Waterloo in Canada, where she also worked in structural combinatorics. She is supported in part by an NSERC grant from the government of Canada.

Refreshments will be served.