Polynomial dual network simplex algorithms
DOI10.1007/BF01580615zbMath0784.90097OpenAlexW4294576787WikidataQ57318276 ScholiaQ57318276MaRDI QIDQ689130
James B. Orlin, Serge A. Plotkin, Éva Tardos
Publication date: 6 December 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580615
transshipment problemminimum cost network flowspolynomial dual network simplex pivot rulestrongly polynomial capacity scaling algorithms
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)
Related Items (10)
Cites Work
- A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
- Signature Methods for the Assignment Problem
- On the simplex algorithm for networks and generalized networks
- Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
- Theoretical Properties of the Network Simplex Method
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Polynomial dual network simplex algorithms