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

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) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (10)

Probability Distributions on Partially Ordered Sets and Network Interdiction Games ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ A new strongly polynomial dual network simplex algorithm ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ Flow constrained minimum cost flow problem ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ A new scaling algorithm for the minimum cost network flow problem ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ Computational experience with exterior point algorithms for the transportation problem

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