Home > Articles > Published articles > A new pivot selection rule for the network simplex algorithm |

Bibliographic citation -- Permanent link: https://ddd.uab.cat/record/112

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. . |

Language: | Anglès. |

Document: | Article ; recerca ; article ; publishedVersion |

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 2017-10-28