An algorithm of the Karmarkar type. (English. Russian original) Zbl 0654.90048

Sov. J. Comput. Syst. Sci. 25, No. 5, 61-74 (1987); translation from Izv. Akad. Nauk SSSR, Tekh. Kibern. 1987, No. 1, 105-118 (1987).
A description is given of a polynomial algorithm for solving linear programming problems that, like Karmarkar’s algorithm, is based on the use of projective transformations of the condition polyhedron. This algorithm has the same estimates of the rate of convergence as Karmarkar’s method but does not require a priori knowledge of an admissible plan or the optimal value of the objective functional.


90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods