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

  • Laszlo Lovasz | London School of Economics

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.

Speaker Details

Laszlo Vegh completed his PhD in mathematics at the Eotvos University in Budapest in 2010, working in the Egervary Research Group on Combinatorial Optimization. He did a postdoc at the Georgia Institute of Technology in 2011-12. Currently he is a lecturer (assistant professor) at the London School of Economics. He is interested in fundamental questions in combinatorial optimization related to connectivity, flows, matchings and matroids, and also applications to areas such as mathematical economics, algorithmic game theory and network design

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks