The expected number of extreme points of a random linear program (Q4726040)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3999651
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The expected number of extreme points of a random linear program |
scientific article; zbMATH DE number 3999651 |
Statements
The expected number of extreme points of a random linear program (English)
0 references
1986
0 references
random linear program
0 references
random polytope
0 references
extreme points
0 references
average case algorithmic performance measures
0 references
0.8998083
0 references
0.8861237
0 references
0.8848045
0 references
0.8811326
0 references
0 references
0.87517524
0 references
There has been increasing attention recently on average case algorithmic performance measures since worst case measures can be qualitatively quite different. An important characteristic of a linear program, relating to simplex method performance, is the number of vertices of the feasible region. We show \(2^ n\) to be an upper bound on the mean number of extreme points of a randomly generated feasible region with arbitrary probability distributions on the constraint matrix and right hand side vector. The only assumption made is that inequality directions are chosen independently in accordance with a series of independent fair coin tosses.
0 references