zbMATH — the first resource for mathematics

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. (English) Zbl 1286.05063
Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 27-40 (2012).
Summary: 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 every 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. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher’s market with linear and with spending constraint utilities. We thereby 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 [D. S. Hochbaum, Math. Oper. Res. 19, No. 2, 390–409 (1994; Zbl 0820.90082)] and in [Tardos, Oper. Res. 34, 250–256 (1986; Zbl 0626.90053)], 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(mn^{3} +m^{2}(m+n \log n) \log m)\) for spending constraint utilities.
For the entire collection see [Zbl 1257.68019].
Reviewer: Reviewer (Berlin)

05C21 Flows in graphs
91B26 Auctions, bargaining, bidding and selling, and other market models
Full Text: DOI