Article ID: | iaor20021405 |
Country: | Netherlands |
Volume: | 27 |
Issue: | 5 |
Start Page Number: | 199 |
End Page Number: | 207 |
Publication Date: | Dec 2000 |
Journal: | Operations Research Letters |
Authors: | McCormick S. Thomas, Shioura Akiyoshi |
This paper shows that the minimum ratio canceling algorithm of Wallacher (and a faster relaxed version) can be generalized to an algorithm for general linear programs with geometric convergence. This implies that when we have a negative cycle oracle, this algorithm will compute an optimal solution in (weakly) polynomial time. We then specialize the algorithm to linear programming on unimodular linear spaces, and to the minimum cost flow and (dual) tension problems. We construct instances proving that even in the network special cases the algorithm is not strongly polynomial.