Random polytopes: Their definition, generation and aggregate properties

Show simple item record

dc.contributor.author May, Jerrold H. en_US
dc.contributor.author Smith, Robert L. en_US
dc.date.accessioned 2006-09-11T19:32:33Z
dc.date.available 2006-09-11T19:32:33Z
dc.date.issued 1982-12 en_US
dc.identifier.citation May, Jerrold H.; Smith, Robert L.; (1982). "Random polytopes: Their definition, generation and aggregate properties." Mathematical Programming 24(1): 39-54. <http://hdl.handle.net/2027.42/47911> en_US
dc.identifier.issn 0025-5610 en_US
dc.identifier.issn 1436-4646 en_US
dc.identifier.uri http://hdl.handle.net/2027.42/47911
dc.description.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 where n 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. en_US
dc.format.extent 819687 bytes
dc.format.extent 3115 bytes
dc.format.mimetype application/pdf
dc.format.mimetype text/plain
dc.language.iso en_US
dc.publisher Springer-Verlag; The Mathematical Programming Society, Inc. en_US
dc.subject.other Operation Research/Decision Theory en_US
dc.subject.other Numerical and Computational Methods en_US
dc.subject.other Random Polytopes en_US
dc.subject.other Optimization en_US
dc.subject.other Problem Generation en_US
dc.subject.other Mathematical and Computational Physics en_US
dc.subject.other Aggregate Polytope Properties en_US
dc.subject.other Combinatorics en_US
dc.subject.other Numerical Analysis en_US
dc.subject.other Mathematics of Computing en_US
dc.subject.other Mathematics en_US
dc.subject.other Linear Programming en_US
dc.subject.other Mathematical Methods in Physics en_US
dc.subject.other Calculus of Variations and Optimal Control en_US
dc.title Random polytopes: Their definition, generation and aggregate properties en_US
dc.type Article en_US
dc.subject.hlbsecondlevel Mathematics en_US
dc.subject.hlbtoplevel Science en_US
dc.description.peerreviewed Peer Reviewed en_US
dc.contributor.affiliationum Department of Industrial and Operations Engineering, The University of Michigan, 48109, Ann Arbor, MI, USA en_US
dc.contributor.affiliationother Graduate School of Business, University of Pittsburgh, 15260, Pittsburgh, PA, USA en_US
dc.contributor.affiliationumcampus Ann Arbor en_US
dc.description.bitstreamurl http://deepblue.lib.umich.edu/bitstream/2027.42/47911/1/10107_2005_Article_BF01585093.pdf en_US
dc.identifier.doi http://dx.doi.org/10.1007/BF01585093 en_US
dc.identifier.source Mathematical Programming en_US
dc.owningcollname Interdisciplinary and Peer-Reviewed
 Show simple item record

This item appears in the following Collection(s)

Search Deep Blue

Advanced Search

Browse by

My Account


Available Now

MLibrary logo