Theoretical Properties of the Network Simplex Method

DOI10.1287/MOOR.4.2.196MaRDI QIDQ4199852zbMATH OpenOpenAlexFDO

Authors William H. Cunningham

Publication date 1979

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.4.2.196

zbMATH Keywords

computational complexitypivotingcyclingspanning treenetwork simplex methodstallingminimum cost network flow problemspathological examplesstrongly feasible treesworst-case computation bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph theory (05C99)

Cited in

(38)

• A simplex algorithm for a class of Leontief flow problems
• Improved linear programming methods for checking avoiding sure loss
• A new family of exponential LP problems
• Modeling the satellite placement problem as a network flow problem with one side constraint
• A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• A specialized network simplex algorithm for the constrained maximum flow problem
• A practical anti-degeneracy row selection technique in network linear programming
• A network penalty method
• Efficient solutions for the bicriteria network flow problem
• A network simplex method for the budget-constrained minimum cost flow problem
• A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
• New efficient shortest path simplex algorithm: Pseudo permanent labels instead of permanent labels
• Degeneracy graphs: Theory and applications. An updated survey
• A new pivot selection rule for the network simplex algorithm
• A network simplex algorithm with O(\(n\)) consecutive degenerate pivots
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• The biobjective undirected two-commodity minimum cost flow problem
• Combinatoric classes of the transportation problem and their properties
• An exponential lower bound for Zadeh's pivot rule
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• Selected bibliography on degeneracy
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• A strongly polynomial simplex method for the linear fractional assignment problem
• The biobjective minimum cost flow problem
• A competitive (dual) simplex method for the assignment problem
• A survey of dynamic network flows
• On cycling in the network simplex method
• A least-squares minimum-cost network flow algorithm
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• A genuinely polynomial primal simplex algorithm for the assignment problem
• Polynomial dual network simplex algorithms
• On the solution of highly degenerate linear programmes
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• An exponential lower bound for Cunningham's rule
• Affirmative action algorithms
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• Degeneracy in transportation problems

This page was built for publication: Theoretical Properties of the Network Simplex Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4199852)