×

An asymptotic estimate of the average number of steps of the parametric simplex method. (English. Russian original) Zbl 0621.90046

U.S.S.R. Comput. Math. Math. Phys. 26, No. 3, 104-113 (1986); translation from Zh. Vychisl. Mat. Mat. Fiz. 26, No. 6, 813-826 (1986).
Summary: An estimate of the average number of steps of the parametric version of the simplex method for solving linear programming problems with respect to some natural class of statistics in the space of the problems is solved. If the number of variables in the problem equals \(n\), and the number of limitations of the equality type equals \(k\), then for the average number of steps \(s(n,k)\) the following estimate holds: \[ s(n,k)\leq \frac{(k+1)^{1/2}}{2}(\pi \ln n)^{k/2}+O((\ln n)^{(k-1)/2}),\quad n\to \infty. \] The Grassmann approach to similar problems, which is important in itself, is described.

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI