Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
复制标题
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
László A. Végh
中科院分区：
文献类型：
--
作者：
László A. Végh
最小费用流问题的非线性扩展是在可行流f上最小化目标∑ij∈E Cij（fij），其中在网络的每个弧ij上，Cij是凸函数。我们给出了一个强多项式算法，找到一个广泛的一类这样的问题的精确的最优解。该类的关键特征是，只要有它的支持，就可以精确地计算出最优解。这包括可分离的凸二次目标和某些市场均衡问题：具有线性和支出约束效用的费雪市场。因此，我们给出了第一个强多项式算法的可分离的二次最小费用流和费氏市场与支出约束的效用，解决公开的问题，例如在[15]和[35]，分别。运行时间为O（m4 log m）的二次成本，O（n4+n2（m+n log n）log n）的Fisher市场的线性效用和O（mn3 +m2（m+n log n）log m）的支出约束效用.
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective ∑ij∈E Cij(fij) over feasible flows f, where on every arc ij of the network, Cij 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 [15] and in [35], respectively. The running time is O(m4 log m) for quadratic costs, O(n4+n2(m+n log n) log n) for Fisher's markets with linear utilities and O(mn3 +m2(m+n log n) log m) for spending constraint utilities.