Joint ORIE Colloquium / Computer Science Theory Seminar

Laci VeghLondon School of Economics and Political Science
A simpler and faster strongly polynomial algorithm for generalized flow maximization

Monday, August 28, 2017 - 4:00pm
Gates 122

Generalized flows are a classical extension of network flows, where the flow gets multiplied by a certain gain or loss factor while traversing an arc. This is a widely applicable model, as the factors can be used to model physical changes such as leakage or theft; or alternatively, they can represent conversions between different types of entities, e.g. different currencies. In the talk, I present a new strongly polynomial algorithm for generalized flow maximization. Besides improving on the running time of the previous strongly polynomial algorithm by a factor O(n^2), the algorithm is also substantially simpler.

This is joint work with Neil Olver (VU Amsterdam).