A simpler and faster strongly polynomial algorithm for generalized flow maximization

DOI10.1145/3055399.3055439MaRDI QIDQ4977964zbMATH OpenOpenAlexFDO

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

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.01778, https://ir.cwi.nl/pub/26543

zbMATH Keywords

network flowstrongly polynomial algorithmgeneralized flowflow maximization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Flows in graphs (05C21)

Abstract: We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [V'egh16]. For the uncapacitated problem formulation, the complexity bound $O(mn(m+nlogn)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.

Recommendations

• A simpler and faster strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial algorithm for generalized flow maximization
• scientific article; zbMATH DE number 1187161
• New algorithms for generalized network flows

Cited in

(15)

• scientific article; zbMATH DE number 1187161 (Why is no real title available?)
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• scientific article; zbMATH DE number 66616 (Why is no real title available?)
• A faster polynomial algorithm for the constrained maximum flow problem
• A simpler and faster strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
• A Polynomial Algorithm for Weighted Abstract Flow
• A strongly polynomial algorithm for generalized flow maximization
• Iteratively reweighted least squares and slime mold dynamics: connection and convergence
• A strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial contraction-expansion algorithm for network flow problems
• SOFSEM 2004: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 871948 (Why is no real title available?)
• A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
• Generalized maximum flow over time with intermediate storage

This page was built for publication: A simpler and faster strongly polynomial algorithm for generalized flow maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977964)