A polynomial time primal network simplex algorithm for minimum cost flows
From MaRDI portal
Publication:1373741
DOI10.1007/BF02614365zbMATH Open0888.90058OpenAlexW3139172074WikidataQ57318274 ScholiaQ57318274MaRDI QIDQ1373741FDOQ1373741
Authors: 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
Recommendations
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Network flows. Theory, algorithms, and applications.
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Title not available (Why is that?)
- Finding Minimum-Cost Circulations by Successive Approximation
- A strongly polynomial minimum cost circulation algorithm
- Finding minimum-cost flows by double scaling
- On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- A new strongly polynomial dual network simplex algorithm
- Technical Note—A Polynomial Simplex Method for the Assignment Problem
- The Scaling Network Simplex Algorithm
- Efficient Shortest Path Simplex Algorithms
- A genuinely polynomial primal simplex algorithm for the assignment problem
- Polynomial dual network simplex algorithms
- A network simplex method
- 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
- A bad network problem for the simplex method and other minimum cost flow algorithms
- Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
Cited In (55)
- A data-dependent approach for high-dimensional (robust) Wasserstein alignment
- An efficient algorithm for two-stage capacitated time minimization transportation problem with restricted flow
- Minimal number of periodic orbits for non-singular Morse-Smale flows in odd dimension
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- On the Length of Monotone Paths in Polyhedra
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal Distributed Searching in the Plane with and Without Uncertainty
- Title not available (Why is that?)
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- The diameters of network-flow polytopes satisfy the Hirsch conjecture
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- One-dimensional service networks and batch service queues
- \textsc{Hide} \& \textsc{Seek}: privacy-preserving rebalancing on payment channel networks
- Explainability of probabilistic bisimilarity distances for labelled Markov chains
- Pricing and clearing combinatorial markets with singleton and swap orders. Efficient algorithms for the futures opening auction problem
- Scheduling in-house transport vehicles to feed parts to automotive assembly lines
- On sub-determinants and the diameter of polyhedra
- A network simplex method for the budget-constrained minimum cost flow problem
- 3/4-Discrete Optimal Transport
- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
- 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
- A fast polynomial time algorithm for logistics network flows
- GNU Oflox: an academic software for the minimal cost network flow problem
- The Scaling Network Simplex Algorithm
- A network simplex algorithm with O(\(n\)) consecutive degenerate pivots
- Exterior point simplex-type algorithms for linear and network optimization problems
- A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks
- Budget-feasible mechanisms for proportionally selecting agents from groups
- A POLYNOMIAL-TIME DUAL SIMPLEX ALGORITHM FOR THE MINIMUM COST FLOW PROBLEM
- Modular circulation and applications to traffic management
- An iterative security game for computing robust and adaptive network flows
- A note on a generalized network flow model for manufacturing process
- Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
- Balanced-flow algorithm for path network planning in hierarchical spaces
- A strongly polynomial simplex method for the linear fractional assignment problem
- Diagnosing Infeasibility in Min-cost Network Flow Problems Part II: Primal Infeasibility
- Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
- A least-squares minimum-cost network flow algorithm
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- A simplex algorithm for network flow problems with piecewise linear fractional objective function
- Quadratically Regularized Optimal Transport on Graphs
- Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
- Deciding probabilistic bisimilarity distance one for probabilistic automata
- The octatope abstract domain for verification of neural networks
- An exterior simplex type algorithm for the minimum cost network flow problem
- New polynomial-time cycle-canceling algorithms for minimum-cost flows
- EMDUniFrac: exact linear time computation of the UniFrac metric and identification of differentially abundant organisms
- Solving the moving target search problem using indistinguishable searchers
- Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
- Title not available (Why is that?)
- Random walks on the vertices of transportation polytopes with constant number of sources
- A novel approach to subgraph selection with multiple weights on arcs
This page was built for publication: A polynomial time primal network simplex algorithm for minimum cost flows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1373741)
