Polynomial dual network simplex algorithms

DOI10.1007/BF01580615MaRDI QIDQ689130zbMATH OpenOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

transshipment problemminimum cost network flowspolynomial dual network simplex pivot rulestrongly polynomial capacity scaling algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

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

Cites work

• scientific article; zbMATH DE number 432783 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
• On the simplex algorithm for networks and generalized networks
• Signature Methods for the Assignment Problem
• Theoretical Properties of the Network Simplex Method
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Cited in

(14)

• 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
• Advantageous Properties of Dual Transhipment Polyhedra
• A polynomial time primal network simplex algorithm for minimum cost flows
• The Scaling Network Simplex Algorithm
• Exterior point simplex-type algorithms for linear and network optimization problems
• Polynomial algorithms for the synthesis of bounded nets
• 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

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)