A Modified Layered-Step Interior-Point Algorithm for Linear Programming

N. Megiddo, S. Mizuno and T. Tsuchiya

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrix $A$. The main drawback of the algorithm is the use of an unknown big constant $\bar \chi_A$ in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when an well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal-dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye.

Contact: megiddo@almaden.ibm.ac.jp, tsuchiya@sun312.ism.ac.jp, mizuno@ism.ac.jp

IBM Technical Report.