A new pivot selection rule for the network simplex algorithm
Sokkalingam, P. T.
Sharma, Prabha
Ahuja, Ravindra K.

Data: 1997
Resum: We present a new network simplex pivot selection rule, which we call the minimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks with n nodes, m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(n(Delta)) pivots and in O((Delta)(m + n log n)) time, where (Delta) is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n^2) pivots and O(nm + n^2 log n) time. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Networks ; Simplex algorithm ; Minimum cost flow problem ; Assignment problem ; Shortest path problem
Publicat a: Mathematical Programming, vol. 78 n. 2 (1997) p. 149-158, ISSN 0025-5610

10 p, 591.4 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir