A scaling-invariant interior-point algorithm is presented for linear programming whose iteration-complexity and arithmetic-complexity are bounded by a polynomial of the dimension and the logarithm of a certain condition number of the linear programming constraint matrix. In the iteration of the algorithm, the affine scaling direction is computed and a test involving this direction is performed to determine whether the trust-region step is needed.
If the trust-region direction is not needed then a step along the affine scaling direction is taken followed by a standard corrector step. Otherwise, the affine scaling direction determines a scaling-invariant bipartition of the variables which allows to construct a pair of primal and dual trust-region subproblems whose optimal solutions yield the trust-region direction. Then the algorithm takes a step along either the affine scaling or the trust-region direction whichever yields the largest duality gap reduction.