TY - GEN
T1 - A simpler and faster strongly polynomial algorithm for generalized flow maximization
AU - Olver, N.K.
AU - Végh, László
PY - 2017
Y1 - 2017
N2 - We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given very recently by Végh; our new algorithm is much simpler, and much faster. The complexity bound O((m + nlogn)mnlog(n2/m)) improves on the previous estimate obtained by Végh by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
AB - We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given very recently by Végh; our new algorithm is much simpler, and much faster. The complexity bound O((m + nlogn)mnlog(n2/m)) improves on the previous estimate obtained by Végh by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
KW - Generalized flow
KW - Network flow
KW - Strongly polynomial
UR - http://www.scopus.com/inward/record.url?scp=85024364692&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024364692&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055439
DO - 10.1145/3055399.3055439
M3 - Conference contribution
SP - 100
EP - 111
BT - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC)
PB - ACM
ER -
