EUVIMEDEUVIMED entdecken
Crossref

A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization

Neil Olver, László A. Végh

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →