A simpler and faster strongly polynomial algorithm for generalized flow maximization
A simpler and faster strongly polynomial algorithm for generalized flow maximization
复制标题
一种更简单、更快速的广义流最大化的强多项式算法
DOI：
10.1145/3055399.3055439
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Olver N
中科院分区：
文献类型：
--
作者：
Olver N
我们提出了一种新的广义流最大化的强多项式算法，该算法比以前的强多项式算法要简单和快得多[34]。对于无能力问题的形式，复杂性界O(Mn(m+nlogn)log(n2/m))比先前的估计提高了几乎一个因子O(N2)。即使对于较小的数值参数值，我们的运行时间界也可以与最好的弱多项式算法相媲美。新的关键技术思想是放宽原有的可行性条件。这使得我们几乎可以完全处理整体流，这与以前解决该问题的所有算法形成了鲜明对比。
We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [34]. For the uncapacitated problem formulation, the complexity boundO(mn(m+nlogn)log (n2/m)) improves on the previous estimate by almost a factorO(n2). Even for small numerical parameter values, our running time bound is comparable to the best weakly polynomial algorithms. The key new technical idea is relaxing the primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
登录
查看更多内容
通过收缩网络来改善最大广义流计算的时间限制
影响因子：
1.1
作者：
T. Radzik
通讯作者：
T. Radzik
广义最大流问题的简单 GAP 消除算法
DOI：
--
发表时间：
2006
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Mateo Restrepo;David P. Williamson
通讯作者：
David P. Williamson
影响因子：
2.7
作者：
D. Goldfarb;Zhiying Jin;Yiqing Lin
通讯作者：
Yiqing Lin
DOI：
--
发表时间：
1998
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
作者：
É. Tardos;Kevin Wayne
通讯作者：
Kevin Wayne
凹广义流及其在市场均衡中的应用
DOI：
10.1287/moor.2013.0623
发表时间：
2011
期刊：
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh