On nonnegative solutions of random systems of linear inequalities (Q1091261)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On nonnegative solutions of random systems of linear inequalities
scientific article

    Statements

    On nonnegative solutions of random systems of linear inequalities (English)
    0 references
    0 references
    1987
    0 references
    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.
    0 references
    random inequalities
    0 references
    expected number of basic feasible solutions
    0 references
    upper bounds
    0 references

    Identifiers