Random polytopes: Their definition, generation and aggregate properties
 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. 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