ISSN:
1436-4646
Keywords:
Random Polytopes
;
Linear Programming
;
Problem Generation
;
Aggregate Polytope Properties
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 2 n 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585093
Permalink
