Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks

Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

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