Speaker Laszlo Lovasz
Affiliation London School of Economics
Host Nikhil Devanur Rangarajan
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.