Joint ORIE Colloquium - CS Theory Seminar: Laci Vegh (London School of Economics) - A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization

Monday, August 28, 2017 at 4:00pm

Bill and Melinda Gates Hall, 122
107 Hoy Rd, Ithaca, NY 14850

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).

Event Type



College of Engineering, Computer Science, Operations Research and Information Engineering, Computing and Information Science


engineering, operations research, orie, Computer Science, College of Engineering



Laci Vegh

Speaker Affiliation

Department of Mathematics, London School of Economics


Recent Activity