A polynomial dual simplex algorithm for the generalized circulation problem

A polynomial dual simplex algorithm for the generalized circulation problem

0.00 Avg rating0 Votes
Article ID: iaor2003721
Country: Germany
Volume: 91
Issue: 2
Start Page Number: 271
End Page Number: 288
Publication Date: Jan 2002
Journal: Mathematical Programming
Authors: , ,
Keywords: programming: linear
Abstract:

This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem.

Reviews

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