Theoretical Properties of the Network Simplex Method
From MaRDI portal
Publication:4199852
computational complexitycyclingminimum cost network flow problemsnetwork simplex methodpathological examplespivotingspanning treestallingstrongly feasible treesworst-case computation bounds
Graph theory (05C99) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Linear programming (90C05) Programming involving graphs or networks (90C35)
Cited in
(40)- A strongly polynomial simplex method for the linear fractional assignment problem
- Degeneracy in transportation problems
- A new family of exponential LP problems
- On the solution of highly degenerate linear programmes
- A network penalty method
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
- Efficient solutions for the bicriteria network flow problem
- Selected bibliography on degeneracy
- Degeneracy graphs: Theory and applications. An updated survey
- Combinatoric classes of the transportation problem and their properties
- A practical anti-degeneracy row selection technique in network linear programming
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- A new pivot selection rule for the network simplex algorithm
- A simplex algorithm for a class of Leontief flow problems
- The biobjective minimum cost flow problem
- Improved linear programming methods for checking avoiding sure loss
- A network simplex method for the budget-constrained minimum cost flow problem
- A network simplex algorithm with O(\(n\)) consecutive degenerate pivots
- On cycling in the network simplex method
- Affirmative action algorithms
- A competitive (dual) simplex method for the assignment problem
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- An exponential lower bound for Cunningham's rule
- Exponential lower bounds for history-based simplex pivot rules on abstract cubes
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- A specialized network simplex algorithm for the constrained maximum flow problem
- A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
- An exponential lower bound for Zadeh's pivot rule
- A least-squares minimum-cost network flow algorithm
- A genuinely polynomial primal simplex algorithm for the assignment problem
- Polynomial dual network simplex algorithms
- A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses
- On the number of degenerate simplex pivots
- The biobjective undirected two-commodity minimum cost flow problem
- On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
- On the number of degenerate simplex pivots
- Modeling the satellite placement problem as a network flow problem with one side constraint
- New efficient shortest path simplex algorithm: Pseudo permanent labels instead of permanent labels
- A survey of dynamic network flows
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)
