Theoretical Properties of the Network Simplex Method
From MaRDI portal
Publication:4199852
computational complexitypivotingcyclingspanning treenetwork simplex methodstallingminimum cost network flow problemspathological examplesstrongly feasible treesworst-case computation bounds
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
(40)- 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
- On the number of degenerate simplex pivots
- 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
- On the number of degenerate simplex 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)
