Neil Olver (London School of Economics adn Political Science)

Title: Generalized flow, the net present value problem, and an open question in arithmetic computation

Abstract:
In the maximum generalized flow problem, the goal is to send as much flow as possible through a given network, but with the additional ingredient that flow is scaled as it traverses each arc. The model is very classical, dating back to the paper by Kantorovich that introduced the notion of linear programming. Only recently, a strongly polynomial algorithm for this problem -- an algorithm that is efficient in a certain refined sense -- was provided by Végh. We give a new strongly polynomial algorithm that is both substantially faster and dramatically simpler. I will discuss the implications of our result for a classical problem in project scheduling, and how this brings to light a new algorithmic question in arithmetic.

(Includes joint work with L. Végh, as well as J. Correa, A. Schulz and L. Végh.)