Random polytopes: Their definition,generation and aggregate properties |
| |
Authors: | Jerrold H. May Robert L. Smith |
| |
Affiliation: | (1) Graduate School of Business, University of Pittsburgh, 15260 Pittsburgh, PA, USA;(2) Department of Industrial and Operations Engineering, The University of Michigan, 48109 Ann Arbor, MI, USA |
| |
Abstract: | The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2n wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints. |
| |
Keywords: | Random Polytopes Linear Programming Problem Generation Aggregate Polytope Properties |
本文献已被 SpringerLink 等数据库收录! |
|