A simpler and faster strongly polynomial algorithm for generalized flow maximization

DOI10.1145/3055399.3055439zbMATH Open1370.05203arXiv1611.01778OpenAlexW2555036241MaRDI QIDQ4977964FDOQ4977964

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)

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.

Full work available at URL: https://arxiv.org/abs/1611.01778

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

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)

Cited In (15)

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

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)