A Strongly Polynomial Algorithm for Generalized Flow Maximization
From MaRDI portal
Publication:2976148
DOI10.1287/moor.2016.0800zbMath1359.90123OpenAlexW2524112391MaRDI QIDQ2976148
Publication date: 13 April 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: http://eprints.lse.ac.uk/69679/1/Vegh_Strongly%20polynomial.pdf
Programming involving graphs or networks (90C35) Linear programming (90C05) Combinatorial optimization (90C27) Paths and cycles (05C38)
Related Items
Unnamed Item, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Cites Work
- A strongly polynomial minimum cost circulation algorithm
- New algorithms for generalized network flows
- Combinatorial interior point methods for generalized network flow problems
- Monotonizing linear programs with up to two nonzeroes per column
- Improving time bounds on maximum generalised flow computations by contracting the network
- Speeding up Karmarkar's algorithm for multicommodity flows
- Optimum flows in general communication networks
- Mathematical Methods of Organizing and Planning Production
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Combinatorial Algorithms for the Generalized Circulation Problem
- Finding minimum-cost circulations by canceling negative cycles
- New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
- A Strongly Polynomial Algorithm for a Special Class of Linear Programs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- On Max Flows with Gains and Pure Min-Cost Flows
- Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
- A SURVEY OF COMBINATORIAL MAXIMUM FLOW ALGORITHMS ON A NETWORK WITH GAINS(<Special Issue>Network Design, Control and Optimization)
- A Faster Combinatorial Algorithm for the Generalized Circulation Problem
- Concave Generalized Flows with Applications to Market Equilibria
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- Max flows in O(nm) time, or better
- On the equivalence of some generalized network problems to pure network problems
- A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
- A simple GAP-canceling algorithm for the generalized maximum flow problem
- Fast and simple approximation schemes for generalized flow.
- A polynomial dual simplex algorithm fot the generalized circulation problem.
