ISSN:
1436-4646
Keywords:
Random linear program
;
random polytope
;
extreme points
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01580643
Permalink
