- 1.R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows. Prentice-Hall, Englewood Cliffs, 1993Google Scholar
- 2.R.D. Armstrong and Z. Jin. A new strongly polynomial dual network simplex algorithm. Mathematical Programming 78 (1997), 131-148 Google ScholarDigital Library
- 3.J. Edmonds and R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the A CM 19 (1972), 248-264 Google ScholarDigital Library
- 4.T.R. Ervolina and S.T. McCormick. Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discrete Applied Mathematics 46 (1993), 133- 165 Google ScholarDigital Library
- 5.M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization problems. Journal of the ACM 34 (1987), 596-615 Google ScholarDigital Library
- 6.H.N. Gabow. Scaling algorithms for network problems. Journal of Computer and Systems Sciences 31 (1985), 148-168 Google ScholarDigital Library
- 7.R. Hassin. The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm. Mathematical Programming 25 (1983), 228-239Google ScholarCross Ref
- 8.B. Korte, J. Vygen. Combinatorial Optimization: The. ory and Algorithms. Springer, Berlin, 2000Google Scholar
- 9.J.B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations Research 41 (1993), 338-350 Google ScholarDigital Library
- 10.J.B. Orlin, S.A. Plotkin, and 1~,. Tardos. Polynomial dual network simplex algorithms. Mathematical Programming 60 (1993), 255-276 Google ScholarDigital Library
- 11.S.A. Plotkin and 15',. Tardos. Improved dual network simplex. Proceedings of the 1st Annual A CM-$IAM Symposium on Discrete Algorithms (1990), 367-376 Google ScholarDigital Library
- 12.M. Shigeno, S. Iwata, and S.T. McCormick. Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow. ManuscriptGoogle Scholar
- 13.E'. Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5 (1985), 247-255 Google ScholarDigital Library
Index Terms
- On dual minimum cost flow algorithms (extended abstract)
Recommendations
Equivalence of the primal and dual simplex algorithms for the maximum flow problem
In this paper, we study the primal and dual simplex algorithms for the maximum flow problem. We show that any primal simplex algorithm for the maximum flow problem can be converted into a dual simplex algorithm that performs the same number of pivots ...
Polynomial-time primal simplex algorithms for the minimum cost network flow problem
AbstractWe present two variants of the primal network simplex algorithm which solve the minimum cost network flow problem in at mostO(n2 logn) pivots. Here we define the network simplex method as a method which proceeds from basis tree to adjacent basis ...
An exterior simplex type algorithm for the Minimum Cost Network Flow Problem
In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex ...
Comments