A polynomial time primal network simplex algorithm for minimum cost flows

DOI10.1007/BF02614365zbMath0888.90058OpenAlexW3139172074WikidataQ57318274 ScholiaQ57318274MaRDI QIDQ1373741

James B. Orlin

Publication date: 25 November 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02614365

zbMATH Keywords

mininium cost flowpolynomial time primal network simplex algorithm

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 (42)

Quadratically Regularized Optimal Transport on Graphs ⋮ On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ A minimum cost network flow model for the maximum covering and patrol routing problem ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ A novel approach to subgraph selection with multiple weights on arcs ⋮ An iterative security game for computing robust and adaptive network flows ⋮ Semi-discrete optimal transport: hardness, regularization and numerical solution ⋮ \textsc{Hide} \& \textsc{Seek}: privacy-preserving rebalancing on payment channel networks ⋮ Budget-feasible mechanisms for proportionally selecting agents from groups ⋮ Explainability of probabilistic bisimilarity distances for labelled Markov chains ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ The octatope abstract domain for verification of neural networks ⋮ Unnamed Item ⋮ Solving the moving target search problem using indistinguishable searchers ⋮ A simplex algorithm for network flow problems with piecewise linear fractional objective function ⋮ A least-squares minimum-cost network flow algorithm ⋮ On sub-determinants and the diameter of polyhedra ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ 3/4-Discrete Optimal Transport ⋮ A network simplex method for the budget-constrained minimum cost flow problem ⋮ Scheduling in-house transport vehicles to feed parts to automotive assembly lines ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ Pricing and clearing combinatorial markets with singleton and swap orders. Efficient algorithms for the futures opening auction problem ⋮ EMDUniFrac: exact linear time computation of the UniFrac metric and identification of differentially abundant organisms ⋮ The diameters of network-flow polytopes satisfy the Hirsch conjecture ⋮ A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks ⋮ Random walks on the vertices of transportation polytopes with constant number of sources ⋮ Balanced-flow algorithm for path network planning in hierarchical spaces ⋮ A strongly polynomial simplex method for the linear fractional assignment problem ⋮ Optimal Distributed Searching in the Plane with and Without Uncertainty ⋮ Unnamed Item ⋮ Modular circulation and applications to traffic management ⋮ One-dimensional service networks and batch service queues ⋮ Deciding probabilistic bisimilarity distance one for probabilistic automata ⋮ A note on a generalized network flow model for manufacturing process ⋮ On the Length of Monotone Paths in Polyhedra ⋮ Unnamed Item ⋮ A network simplex algorithm with O(\(n\)) consecutive degenerate pivots ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation

Cites Work

• Unnamed Item
• Unnamed Item
• A genuinely polynomial primal simplex algorithm for the assignment problem
• Polynomial dual network simplex algorithms
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A strongly polynomial minimum cost circulation algorithm
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Finding minimum-cost flows by double scaling
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• A new strongly polynomial dual network simplex algorithm
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• Finding Minimum-Cost Circulations by Successive Approximation
• Technical Note—A Polynomial Simplex Method 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
• The Scaling Network Simplex Algorithm
• A network simplex method
• A bad network problem for the simplex method and other minimum cost flow algorithms
• Efficient Shortest Path Simplex Algorithms
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm

This page was built for publication: A polynomial time primal network simplex algorithm for minimum cost flows