...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Computing >A STRONGLY POLYNOMIAL ALGORITHM FOR A CLASS OF MINIMUM-COST FLOW PROBLEMS WITH SEPARABLE CONVEX OBJECTIVES
【24h】

A 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 to minimize the objective Sigma(ij is an element of Epsilon) 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 the case when all C-ij's are convex quadratic functions, settling an open problem raised, e.g., by Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities that can be formulated in this framework (see Shmyrev [J. Appl. Ind. Math., 3 (2009), pp. 505-518], Birnbaum, Devanur, and Xiao [Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 127-136]). For the latter class this resolves an open question raised by Vazirani [Math. Oper. Res., 35 (2010), pp. 458-478]. 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) logm) for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.
机译：对最小成本流问题进行充分研究的非线性扩展是在可行流f上最小化目标Sigma（ij是Epsilon的元素）C-ij（f（ij）），其中在网络的每个弧ij上， C-ij是一个凸函数。对于所有C-ij都是凸二次函数的情况，我们给出了一个强多项式算法，以解决例如由Hochbaum [Math。歌剧Res。，19（1994），第390-409页]。我们还提供了用于在Fisher市场中使用线性效用和支出约束效用来计算市场均衡的强多项式算法，这些算法可以在此框架中制定（参见Shmyrev [J. Appl。Ind。Math。，3（2009），pp。505- 518]，Birnbaum，Devanur和Xiao [第12届ACM电子商务会议论文集，2011年，第127-136页]。对于后一类，这解决了Vazirani [数学。歌剧，第35卷（2010），第458-478页]。对于二次成本，运行时间为O（m（4）log m），对于具有线性效用的Fisher市场，运行时间为O（n（4）+ n（2）（m + n log n）log n），而O（mn（ 3）+ m（2）（m + n log n）logm）用于支出约束工具。所有这些算法都在解决一般问题设置的通用框架中提出。尽管即使在近似意义上也无法针对一般问题给出强多项式算法（请参阅Hochbaum [Math。Oper。Res。，19（1994），pp。390-409]），但我们证明了假设存在某些黑匣子预言机，只能使用大量多项式算术运算和预言机调用来给出一种算法。可以通过在各自的设置中实现这些预言来得出特定的算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号