event
ARC Seminar - László Végh - Georgia Tech
Primary tabs
Abstract
A well-studied nonlinear extension of the minimum-cost flow problemis to minimize the objective \sum_{ij\in E} C_{ij}(f_{ij}) over feasible flows f, where on each arc ij of the network, C_{ij} is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems, The class includes convex quadratic objectives; thereby we give the first strongly polynomial algorithms for separable convex quadratic
minimum-cost flows, settling a long-standing open question. Further applications include market equilibrium problems, in particular, we give the first strongly polynomial algorithm for Fisher's market with spending constraint utilities.
Groups
Status
- Workflow Status:Published
- Created By:Elizabeth Ndongi
- Created:02/20/2012
- Modified By:Fletcher Moore
- Modified:10/07/2016
Categories
Keywords
- No keywords were submitted.