A monotonic projective algorithm for fractional linear programming (Q580191): Difference between revisions

The purpose of this paper is to demonstrate that N. Karmarkar's projective algorithm [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] for linear programming is fundamentally an algorithm for fractional linear programming on the simplex. Convergence of the algorithm is established assuming only an initial lower bound on the optimal objective value using either the lower bound construction proposed by the author [Analysis of a modified Karmarkar algorithm for linear programming, Working Paper, Series B 84, Yale School of Oranization and Management, New Haven, CT, 1985.] or a construction proposed by \textit{M. J. Todd} and \textit{B. P. Burrell} [Algorithmica 1, 409-424 (1986; Zbl 0621.90048)]. The author shows that the algorithm can be made monotone and that the monotonic algorithm can be applied to obtain an initial lower bound.