A strongly polynomial algorithm for generalised flow maximisation

21^st October 2014, 13:00 Ashton Lecture Theater
Dr Laszlo Vegh
Department of Management
London School of Economics

Abstract

Generalised 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. The talk presents the first strongly polynomial algorithm for the generalized flow maximisation problem. This used to be the simplest class of linear programmes with no strongly polynomial algorithm known, and finding one has been a longstanding open question. The algorithm is based on a new variant of the classical scaling technique, called continuous scaling.