Vershik, A. M.; Sporyshev, P. V. An estimate of the average number of steps in the simplex method, and problems in asymptotic integral geometry. (English. Russian original) Zbl 0532.90062 Sov. Math., Dokl. 28, 195-199 (1983); translation from Dokl. Akad. Nauk SSSR 271, 1044-1048 (1983). By problems in asymptotic integral geometry we understand here problems on computing the asymptotic behavior of the average values of various functionals of geometric origin from a Grassmann manifold or from other classical homogeneous spaces with respect to an invariant measure, as the dimension n goes to \(\infty\). Linear algebra, linear programming, convex geometry, and so on, provide interesting examples of such problems. A reduction proposed in the 70s by the first author consists in identifying a space of linear programming problems, a space of polyhedra or other objects, with a Grassmann manifold, and the objects themselves with the projection (or section) of a universal object on a given subspace [see the first author, Sov. Math. Surveys 25, No.5, 117-124 (1970; Zbl 0224.90041); the first author and A. G. Chernyakov, Sov. Math., Dokl. 26, 353-356 (1982; Zbl 0522.52004); and the second author, Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 123, 208-220 (1983; Zbl 0521.52009)]. In this note we consider the question of the average number of steps in the refined simplex method when the number of constraints is fixed but the number of variables grows; the number of steps is a function defined (almost everywhere) on a Grassmann manifold, and the integration is with respect to an invariant measure. The answer is that this average does not exceed \(C_ k(\ln n)^{k/2}\) asymptotically as \(n\to \infty\), where \(C_ k\) is a constant, k is the number of constraints, and n is the number of variables. It can be shown by the usual methods that this estimate is realized on an overwhelming (with respect to the measure) number of problems. The refinement of the simplex method used below, which is analogous to that proposed by K.-H. Borgwardt [Oper. Res. Verf. 31, 83-97 (1979; Zbl 0407.90053)], strives for a greater geometrization of the arguments and is described in the usual terms. A communication of work of S. Smale recently appeared in Science 217, 39 (1982) in which an estimate linear in n of the number of steps was announced; however, we do not know the precise statement of the problem Smale studied. Cited in 1 ReviewCited in 4 Documents MSC: 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity 65K05 Numerical mathematical programming methods 52A40 Inequalities and extremum problems involving convexity in convex geometry 52Bxx Polytopes and polyhedra 57R25 Vector fields, frame fields in differential topology 58E17 Multiobjective variational problems, Pareto optimality, applications to economics, etc. Keywords:average number of steps; simplex method; growing number of variables; asymptotic behavior of average values; asymptotic integral geometry; Grassmann manifold; invariant measure Citations:Zbl 0224.90041; Zbl 0522.52004; Zbl 0521.52009; Zbl 0407.90053 PDFBibTeX XMLCite \textit{A. M. Vershik} and \textit{P. V. Sporyshev}, Sov. Math., Dokl. 28, 195--199 (1983; Zbl 0532.90062); translation from Dokl. Akad. Nauk SSSR 271, 1044--1048 (1983)