10th Colloquium of the Research Area C3C3 Kolloquium / Colloquium of the Research Area C3

by László Végh (University of Bonn), Sharat Ibrahimpur (University of Bonn)

Friday Feb 21, 2025, 9:00 AM → 11:00 AM Europe/Berlin

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

09:30

Coffee and Tea

10:00

László Végh: From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

10:45

Coffee break

11:15

Sharat Ibrahimbur: Stochastic Minimum Norm Combinatorial Optimization

 

Abstracts

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^{omega + o(1)}-time strongly polynomial time algorithms for computing a maximum bipartite b-matching where omega<2.38 is the matrix multiplication constant. Additionally, they imply an (m^{1 + 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.

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.

Website: https://www.mathematics.uni-bonn.de/hcm/events/colloquia_c3/coll_10

Research Area: C3 Combinatorial optimization, complexity, and chip design

Colloquium history: https://www.or.uni-bonn.de/hausdorff.html