On nonnegative solutions of random systems of linear inequalities (Q1091261): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3704527 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Note on Random Triangles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coverage problems and random convex hulls / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of vertices of random convex polyhedra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Problem in Geometric Probability. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5561562 / rank | |||
Normal rank |
Latest revision as of 10:39, 18 June 2024
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
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