##
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.