ISSN:
1436-4646
Schlagwort(e):
Random linear program
;
random polytope
;
extreme points
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01580643
Permalink
