
Speaker Laszlo Lovasz Affiliation London School of Economics Host Nikhil Devanur Rangarajan Duration 00:52:56 Date recorded 13 March 2013 A wellstudied nonlinear extension of the minimumcost 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 minimumcost flows and for Fisher's market with spending constraint utilities.
©2013 Microsoft Corporation. All rights reserved.
