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: firstname.lastname@example.org, email@example.com, firstname.lastname@example.org
IBM Technical Report.