×

On nonnegative solutions of random systems of linear inequalities. (English) Zbl 0622.90054

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. 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.
Reviewer: J.Müller

MSC:

90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0604.90092
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Buchta, C.; Hlawka, E. (ed.), Zufällige Polyeder—Eine Übersicht, No. 1114 (1985), Berlin-Heidelberg-New York-Tokyo · Zbl 0582.52005 · doi:10.1007/BFb0101638
[2] S. Halász and D. J. Kleitman, A note on random triangles,Stud. Appl. Math.53 (1974), 225-237. · Zbl 0416.60016
[3] N. P. Jewell and J. R. Romano, Coverage problems and random convex hulls,J. Appl. Probab.19 (1982), 546-561. · Zbl 0504.60014 · doi:10.2307/3213513
[4] A. Prékopa, On the number of vertices of random convex polyhedra,Period. Math. Hungar.2 (1972), 259-282. · Zbl 0282.60007 · doi:10.1007/BF02018666
[5] Schläfli, L., Theorie der vielfachen Kontinuität, 167-387 (1950), Basel · doi:10.1007/978-3-0348-4118-4_13
[6] J. Steiner, Einige Gesetze über die Theilung der Ebene und des Raumes,J. Reine Angew. Math.1 (1826), 349-364. · Zbl 0416.60016 · doi:10.1515/crll.1826.1.349
[7] J. G. Wendel, A problem in geometric probability,Math. Scand.11 (1962), 109-111. · Zbl 0108.31603
[8] S. S. Wilks,Mathematical Statistics, Wiley, New York-London, 1962. · Zbl 0173.45805
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.