ABSTRACT:
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.
BIO:
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.