A complexity reduction for the long-step path-following algorithm for linear programming. (English) Zbl 0763.90064

den Hertog, D.; Roos, C.; Vial, J.-Ph.

SIAM J. Optim. 2, No. 1, 71-87 (1992).

A long-step path-following algorithm is given which provides a \(\sqrt n\) reduction in the complexity bound relative to previous methods. If \(L\) is the length of the input data, complexity bounds are \(O(n^ 3 L)\) or \(O(n^{3,5} L)\).

Reviewer: M.A.Hanson (Tallahassee)

MSC:

90C05	Linear programming
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

long-step path-following algorithm