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

Date: 1997
Abstract: 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. .
Rights: Tots els drets reservats.
Language: Anglès
Document: Article ; recerca ; Versió publicada
Subject: Networks ; Simplex algorithm ; Minimum cost flow problem ; Assignment problem ; Shortest path problem
Published in: Mathematical Programming, vol. 78 n. 2 (1997) p. 149-158, ISSN 0025-5610



10 p, 591.4 KB
 UAB restricted access

The record appears in these collections:
Articles > Research articles
Articles > Published articles

 Record created 2006-03-13, last modified 2023-06-03



   Favorit i Compartir