The expected number of extreme points of a random linear program
Berenguer, Sancho E. (Sancho Eduardo de Bittencourt); Smith, Robert L.
Berenguer, Sancho E.; Smith, Robert L.; (1986). "The expected number of extreme points of a random linear program." Mathematical Programming 35(2): 129-134. <http://hdl.handle.net/2027.42/47914>
AbstractThere 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.
Springer-Verlag; The Mathematical Programming Society, Inc.
MetadataShow full item record
Accessibility: If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.