Dear colleagues,
let me invite you to the next session of our doctoral seminar that will take place tomorrow (7. 12.) at 9:50 in S6.
I will present a paper by Neil Olver and Laszló Végh titled A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization. ( https://arxiv.org/abs/1611.01778 )
The paper presents a new strongly polynomial algorithm for generalized flow maximization. In generalized flow maximization, there are additional gain factors on edges, so that flow can actually multiplicatively change when going through an edge.
Solving generalized flows in strongly polynomial time is an important progress towards showing that general LPs have strongly polynomial algorithms; this is due to the fact that we can use generalized flows to find a feasible solution to an LP of the form Ax=b, x>=0 with A having two arbritrary non-zero entries per column.
The first strongly polynomial algorithm was given by Végh in 2016; the algorithm we will see is a substantial simplification of the first algorithm. The new algorithm also improves qualitatively on the previous one, with a running time bound of O( (m+n log n) mn log(n^2/m) ).
---
Only basic knowledge of maximum flows will be assumed; everyone is welcome.
Last but not least, I'll bring some tea, fruit and cookies at 9:45, so come in on time to get a mini-breakfast!
See you all there, Martin Böhm