Resenhas IME-USP 1995, Vol. 2, No. 2, 197-207.
On the Complexity of Linear Programming
Clovis C. Gonzaga
Department of Mathematics
Federal University of Santa Catarina
Florianópolis, SC
Brazil
E-mail address: clovis@mtm.ufsc.br
Abstract
In this paper we show a simple treatment of the complexity of Linear
Programming. We describe the short step primal-dual path following algorithm
and show that it solves the linear programming problem in O(\sqrt n
L) iterations, each one with a bound of O(n^3) arithmetic
computations.
Back to Table of Contents
Last modified: Sun Oct 29 19:34:45 GMT 1995