On nonnegative solutions of random systems of linear inequalities (Q1091261): Difference between revisions

The number of steps required to solve a linear program by the simplex method turns out be usually much smaller than the theoretical upper bound. In order to explain this phenomenon, in a series of papers the coefficients of linear programs have been considered as random variables. The number of steps is then a further random variable, and its expected value gives information about the ''average-case'' behaviour of the algorithm [cf. \textit{K.-H. Borgwardt}, ''The simplex method. A probabilistic analysis'' (1987; Zbl 0604.90092)]. The author adds to these investigations a new point of view. By determining the expected number of basic feasible solutions he obtains upper bounds for the expected number of steps which - in contrast to previous papers - do not depend on a certain version of the simplex algorithm.