A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Journal of the ACM · 30.04.2020 · 67 (2) · 1-26
DOI: 10.1145/3383454 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 17.04.2020. Verfasst von Neil Olver und 1 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 34 Literaturangaben. Gefördert von: Engineering and Physical Sciences Research Council, European Research Council, Nederlandse Organisatie voor Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
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 allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
Förderung
- Engineering and Physical Sciences Research Council
- European Research Council
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Zitieren
APA
Olver, N., & Végh, L. A. (2020). A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization. Journal of the ACM, 67(2), 1-26. https://doi.org/10.1145/3383454
Vancouver
Olver N, Végh LA. A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization. Journal of the ACM. 2020;67(2):1-26. doi:10.1145/3383454
BibTeX
@article{Olver2020,
author = {Olver, Neil and Végh, László A.},
title = {A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization},
journal = {Journal of the ACM},
year = {2020},
volume = {67},
number = {2},
pages = {1--26},
doi = {10.1145/3383454}
}
EUVIMED