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

Fecha: 1997
Resumen: 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. .
Lengua: Anglès.
Documento: Article ; recerca ; article ; publishedVersion
Materia: Networks ; Simplex algorithm ; Minimum cost flow problem ; Assignment problem ; Shortest path problem
Publicado en: Mathematical Programming, vol. 78 n. 2 (1997) p. 149-158, ISSN 0025-5610



10 p, 591.4 KB
 Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2006-03-13, última modificación el 2017-10-28



   Favorit i Compartir