×

A new polynomial algorithm for linear programming. (English. Russian original) Zbl 0683.90048

Sov. Math., Dokl. 37, No. 1, 264-269 (1988); translation from Dokl. Akad. Nauk SSSR 298, No. 6, 1321-1325 (1988).
There has been a sharp increase in interest in numerical methods of linear programming in recent years. It began with the work of L. G. Khachiyan, who was first to construct the PLP-algorithm( the method of solving the general linear programming problem with rational coefficients which has polynomial complexity as a function of its input description length). Subsequent research as largely stimulated by the desire to find a method which would not only in theory but in reality, on practical problems, surpass the standard simplex method.
In this note one more step in this direction is made - a new PLP- algorithm is constructed. The estimates of its complexity are somewhat worse than those of Karmarkar’s method; however, this does not mean that the actual behavior of our method will also turn out to be worse (after all, the estimates of complexity of Karmarkar’s method are worse than those of Khachiyan’s method for typical cases, while the actual situation turns out to be the opposite).

MSC:

90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite