Polynomial dual network simplex algorithms
DOI10.1007/BF01580615zbMATH Open0784.90097OpenAlexW4294576787WikidataQ57318276 ScholiaQ57318276MaRDI QIDQ689130FDOQ689130
James B. Orlin, Serge 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) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
- Theoretical Properties of the Network Simplex Method
- Signature Methods for the Assignment Problem
- A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- On the simplex algorithm for networks and generalized networks
- Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
Cited In (13)
- A Friendly Smoothed Analysis of the Simplex Method
- Minimum-cost flow algorithms: an experimental evaluation
- A data-dependent approach for high-dimensional (robust) Wasserstein alignment
- A polynomial time primal network simplex algorithm for minimum cost flows
- The Scaling Network Simplex Algorithm
- Polynomial algorithms for the synthesis of bounded nets
- Exterior point simplex-type algorithms for linear and network optimization problems
- Flow constrained minimum cost flow problem
- Strongly polynomial dual simplex methods for the maximum flow problem
- A new scaling algorithm for the minimum cost network flow problem
- Computational experience with exterior point algorithms for the transportation problem
- Probability Distributions on Partially Ordered Sets and Network Interdiction Games
- A new strongly polynomial dual network simplex algorithm
Recommendations
- The Scaling Network Simplex Algorithm 👍 👎
- A new strongly polynomial dual network simplex algorithm 👍 👎
- On strongly polynomial dual simplex algorithms for the maximum flow problem 👍 👎
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem 👍 👎
- On dual minimum cost flow algorithms 👍 👎
This page was built for publication: Polynomial dual network simplex algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q689130)
