A Unified Analytical Approach to Strongly Polynomial Algorithms for Structured Linear ProgramsOberseminar Discrete Optimization

by Bento Natura (Columbia University)

Tuesday Jul 8, 2025, 11:15 AM → 12:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Konferenzraum (Arithmeum / Research Institute for Discrete Mathematics)

Shortest paths, bipartite matching, maximum flow, minimum-cost flow, generalized flows, and discounted Markov decision processes are all central problems in combinatorial optimization. Over the past few decades, each has inspired the development of sophisticated strongly polynomial-time algorithms, often based on tailored methods and distinct algorithmic paradigms.

In a separate line of work, interior-point methods have been progressively refined to yield faster weakly and strongly polynomial-time algorithms for many of these problems. A recent such algorithm, introducing the concept of Straight Line Complexity (SLC), achieves strongly polynomial running time across all of them.

In this talk, we present a self-contained exposition showing how strong polynomiality can be recovered for several of these problems through the lens of SLC analysis.

 

The Oberseminar takes place in the conference room, 2^nd floor. Participants are invited to have coffee or tea in the lounge before.