Strongly polynomial algorithm for a class of minimum-cost flow problems

Опубликовано 27 июля 2016, 0:44

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
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.