A simpler and faster strongly polynomial algorithm for generalized flow maximization

N Olver, LA Végh - Journal of the ACM (JACM), 2020 - dl.acm.org
Journal of the ACM (JACM), 2020dl.acm.org
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 bound O (mn (m+ n log n) log (n 2/m))
improves on the previous estimate by almost a factor O (n 2). 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 …
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 bound O(mn(m+n log n)log (n2/m)) improves on the previous estimate by almost a factor O(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.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果