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. <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 | https://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 |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.