The Variants of Karmarkar's and Simplex Algorithms for Liner Programming

Abstract

We review and modify the Karmarkar's polynomial-time algorithm and its variants for linear programming. These variants are interior point algorithms. Newton barrier methods, and box method. Those algorithms still have polynomial-time computational complexity. For logarithm barrier function algorithm, each iteration updates a penalty parameter and finds an approximate Newton's direction associated with the Kuhn-Tucker system of equations. This paper briefly discusses those algorithms and some extensions of Karmarkar type algorithm to simplex method. We implemented those algorithms in Fortran programs and tested the computational results for iteration numbers and CPU times.