The expected number of extreme points of a random linear program |
| |
Authors: | Sancho E. Berenguer Robert L. Smith |
| |
Affiliation: | (1) Instituto de Matematica Pura e Aplicada, 22460 Rio de Janeiro, Brazil;(2) Department of Industrial and Operations Engineering, The University of Michigan, 48109 Ann Arbor, MI, USA |
| |
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 2n 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.We would like to thank the Institute of Pure and Applied Mathematics in Rio de Janeiro for supporting the authors' collaboration that led to this paper. |
| |
Keywords: | Random linear program random polytope extreme points |
本文献已被 SpringerLink 等数据库收录! |