Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem

Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem

0.00 Avg rating0 Votes
Article ID: iaor19912119
Country: United States
Volume: 16
Start Page Number: 272
End Page Number: 291
Publication Date: Mar 1991
Journal: Mathematics of Operations Research
Authors:
Keywords: computational analysis
Abstract:

The paper studies the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. A pivot selection rule, with a bound of equ1on the number of pivots, is proposed for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in equ2time. In the special case of planar graphs, a polynomial bound on the number of pivots and the running time is obtained. The relaxation of the network simplex algorithm in which cost-increasing pivots are allowed as well as cost-decreasing ones is also considered. For this algorithm a pivot selection rule is proposed with a bound of equ3on the number of pivots, for a network with n vertices, m arcs, and integer arc costs bounded in magnitude by C. The total running time is equ4. This bound is within a logarithmic factor of those of the best previously known algorithms for the minimum-cost circulation problem.

Reviews

Required fields are marked *. Your email address will not be published.