The worst-case step in Karmarkar’s algorithm. (English) Zbl 0674.90060

Anstreicher, Kurt M.

Math. Oper. Res. 14, No. 2, 294-302 (1989).

Let LP denote a linear program on a simplex, \(\overline{LP}\) the transformed program as in the iteration step of Karmarkar’s projective algorithm. The author shows that on every iteration the objective of \(\overline{LP}\) can be reduced by a fraction of 2/n. What concerns the original LP, the guaranteed worst-case reduction in the transformed potential function is approximately 0.72. It is proved that these both bounds are tight.

Reviewer: P.Staniewski

MSC:

90C05	Linear programming
90C06	Large-scale problems in mathematical programming
65K05	Numerical mathematical programming methods

Keywords:

tight bounds; Karmarkar’s projective algorithm; worst-case reduction