Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-21
Computer Science
Data Structures and Algorithms
Minor corrections
Scientific paper
A well-studied nonlinear extension of the minimum-cost flow problem is 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 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, settling open questions posed e.g. in [Hochbaum,94] and in [Vazirani,10], respectively. The running time is O(m^4 log m) for quadratic costs, O(n^4 + n^2(m + n log n)log n) for Fisher's markets with linear utilities and O(m n^3 +m^2(m + n log n) log m) for spending constraint utilities.
No associations
LandOfFree
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-85972