On nonnegative solutions of random systems of linear inequalities
type: Item
instance of: scholarly article
title: On nonnegative solutions of random systems of linear inequalities
zbMATH Open document ID: 0622.90054
DOI: 10.1007/BF02187872
author: Christian Buchta
published in: Discrete \& Computational Geometry
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131011
review text: 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4010207
zbMATH Keywords: random inequalities
zbMATH Keywords: expected number of basic feasible solutions
zbMATH Keywords: upper bounds
MaRDI profile type: Publication
cites work: Q3704527
cites work: A Note on Random Triangles
cites work: Coverage problems and random convex hulls
cites work: On the number of vertices of random convex polyhedra
cites work: A Problem in Geometric Probability.
cites work: Q5561562
Recommended article: On non-negative solutions to large systems of random linear equations
Recommended article: Positive solutions for large random linear systems
Recommended article: Q3403438
Recommended article: Q3540811
Recommended article: Q3696871
Recommended article: Solutions for a system of nonlinear random integral and differential equations
Recommended article: Q4881797
Recommended article: Q4339648
Recommended article: Probabilistic properties of systems of random linear equations over finite algebraic structures
Recommended article: Q4469035
description: scientific article; zbMATH DE number 4010207