Matchings, Maxflows, Matroids
The Power of Augmenting Paths and Computational Models
Time: Wed 2024-11-27 14.00
Location: F3 (Flodis), Lindstedtsvägen 26 & 28, Stockholm
Language: English
Subject area: Computer Science
Doctoral student: Joakim Blikstad , Teoretisk datalogi, TCS
Opponent: Professor Sanjeev Khanna, University of Pennsylvania
Supervisor: Associate professor Danupon Na Nongkai, Teoretisk datalogi, TCS; Associate professor Per Austrin, Teoretisk datalogi, TCS
QC 20241105
Abstract
Matchings, Maximum Flow, and Matroid Intersections are fundamental combinatorial optimization problems that have been studied extensively since the inception of computer science. A series of breakthroughs in graph algorithms and continuous optimization in the past decade has led to exciting almost-optimal algorithms for maximum flow and bipartite matching. However, we are still far from fully understanding these problems. First, it remains open how to solve these problems in modern models of computation, such as parallel, dynamic, online, and communication models. Second, as algorithms become more sophisticated in pursuit of efficiency, they often sacrifice simplicity, potentially obscuring valuable combinatorial insights. This raises a fundamental question: can we develop efficient algorithms that maintain the combinatorial nature of these problems, rather than relying on linear algebra and continuous methods?
This thesis returns to the classic augmenting paths framework---the original approach to matchings, maximum flow, and matroid intersection---with the goal of developing new efficient combinatorial algorithms. Our key contributions include the first combinatorial algorithm achieving almost-linear time for maximum flow on dense graphs, and the first subquadratic independence-query algorithm for matroid intersection. For modern computational models, our contributions include an improved online rounding scheme for fractional matching (leading to an optimal online edge coloring algorithm), a resolution of the query and communication complexity for bipartite matching, and the first sublinear-round parallel algorithms for matroid intersection.