ISSN:
1432-0541
Schlagwort(e):
Simplex method
;
Minimum cost network flows
;
Strongly polynomial
;
Maximum flow
;
Minimum mean augmenting cycle
;
Cost scaling
;
Polytope diameter
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract We present two variants of the primal network simplex algorithm which solve the minimum cost network flow problem in at mostO(n 2 logn) pivots. Here we define the network simplex method as a method which proceeds from basis tree to adjacent basis tree regardless of the change in objective function value; i.e., the objective function is allowed to increase on some iterations. The first method is an extension of theminimum mean augmenting cycle-canceling method of Goldberg and Tarjan. The second method is a combination of a cost-scaling technique and a primal network simplex method for the maximum flow problem. We also show that the diameter of the primal network flow polytope is at mostn 2 m.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01758840
Permalink
