Date: February 21, 2025
Venue: Seminar room, Arithmeum, Lennéstr. 2
Research Area: C3 Combinatorial optimization, complexity, and chip design
Colloquium history: https://www.or.uni-bonn.de/hausdorff.html
Friday, February 21
09:30
Coffee and Tea
10:45
Coffee break
Sharat Ibrahimpur: Stochastic Minimum Norm Combinatorial Optimization
In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. We seek a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm.
We give a general framework for devising approximation algorithms for stochastic minimum-norm optimization, using which we obtain approximation algorithms for the stochastic minimum-norm versions of the load balancing and spanning tree problems.
Based on joint work with Chaitanya Swamy.
László Végh: From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
We provide faster strongly polynomial time algorithms solving maximum flow in structured n-node m-arc networks. Our results imply an an nω+o(1)-time strongly polynomial time algorithms for computing a maximum bipartite b-matching where ω<2.38 is the matrix multiplication constant. Additionally, they imply an (m1+o(1) W)-time algorithm for solving the problem on graphs with a given tree decomposition of width W.
We obtain these results by strengthening and efficiently implementing an approach in Orlin's state-of-the-art O(mn) time maximum flow algorithm from 2013. We develop a general framework that reduces solving maximum flow with arbitrary capacities to (1) solving a sequence of maximum flow problems with polynomial bounded capacities and (2) dynamically maintaining a size-bounded supersets of the transitive closure under edge additions; we call this incremental transitive cover. Our applications follow by leveraging recent weakly polynomial, almost linear time algorithms for maximum flow due to Chen et al. (2022) and van den Brand et al. (2013), and by developing new incremental transitive cover data structures for special cases.
This is joint work with Daniel Dadush, James Orlin, and Aaron Sidford.