Interior path following primal-dual algorithms, part I: Linear programming

The authors describe a primal-dual interior point algorithm for linear programming problems which requires a total of O(√nL) number of iterations, where L is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. [The abstract of Part II is classified under Quadratic Programming.]