Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
Abstract
We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a certain bound on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running time. We also consider the relaxation of the network simplex algorithm in which cost-increasing pivots are allowed as well as cost-decreasing ones. For this algorithm we propose a pivot selection rule with a bound on 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 O(nm logn.min ((lognC),m logn). This bound is competitive with those of previously known algorithms for the minimum- cost circulation problem. (KR)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1988
- Accession Number
- ADA215109
Entities
People
- Robert Tarjan
Organizations
- Princeton University