A polynomial-time algorithm, based on Newton's method, for linear programming (Q1108927)

The paper includes a new interior method for linear optimization problems based on Newton's method. A polynomial time bound is proven for this algorithm. The algorithm is compared with the ellipsoid algorithm and with Karmarkar's algorithm. The proposed algorithm is conceptually simpler than either of those algorithms. Furthermore, the bounds are compared. The most important result is the O \((m+n)L)\) bound on the number of iterations where n is the number of variables and m the number of constraints.