Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Speaker  Laszlo Lovasz

Affiliation  London School of Economics

Host  Nikhil Devanur Rangarajan

Duration  00:52:56

Date recorded  13 March 2013

A well-studied nonlinear extension of the minimum-cost flow problem is that given a convex function on every arc, the objective is to minimize the sum of these function values over feasible flows. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. The class includes convex quadratic objectives and also certain market equilibria problems, such as Fisher's market with linear or with spending constraint utilities. Thereby we give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities.

©2013 Microsoft Corporation. All rights reserved.
> Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives