Cornell University

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

Recent Activity