Show simple item record

The expected number of extreme points of a random linear program

dc.contributor.authorBerenguer, Sancho E. (Sancho Eduardo de Bittencourt)en_US
dc.contributor.authorSmith, Robert L.en_US
dc.date.accessioned2006-09-11T19:32:46Z
dc.date.available2006-09-11T19:32:46Z
dc.date.issued1986-06en_US
dc.identifier.citationBerenguer, Sancho E.; Smith, Robert L.; (1986). "The expected number of extreme points of a random linear program." Mathematical Programming 35(2): 129-134. <http://hdl.handle.net/2027.42/47914>en_US
dc.identifier.issn1436-4646en_US
dc.identifier.issn0025-5610en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/47914
dc.description.abstractThere has been increasing attention recently on average case algorithmic performance measures since worst case measures can be qualitatively quite different. An important characteristic of a linear program, relating to Simplex Method performance, is the number of vertices of the feasible region. We show 2 n to be an upper bound on the mean number of extreme points of a randomly generated feasible region with arbitrary probability distributions on the constraint matrix and right hand side vector. The only assumption made is that inequality directions are chosen independently in accordance with a series of independent fair coin tosses.en_US
dc.format.extent328363 bytes
dc.format.extent3115 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.language.isoen_US
dc.publisherSpringer-Verlag; The Mathematical Programming Society, Inc.en_US
dc.subject.otherMathematical and Computational Physicsen_US
dc.subject.otherNumerical Analysisen_US
dc.subject.otherNumerical and Computational Methodsen_US
dc.subject.otherMathematical Methods in Physicsen_US
dc.subject.otherOptimizationen_US
dc.subject.otherCalculus of Variations and Optimal Controlen_US
dc.subject.otherMathematics of Computingen_US
dc.subject.otherExtreme Pointsen_US
dc.subject.otherCombinatoricsen_US
dc.subject.otherRandom Polytopeen_US
dc.subject.otherRandom Linear Programen_US
dc.subject.otherOperation Research/Decision Theoryen_US
dc.subject.otherMathematicsen_US
dc.titleThe expected number of extreme points of a random linear programen_US
dc.typeArticleen_US
dc.subject.hlbsecondlevelMathematicsen_US
dc.subject.hlbtoplevelScienceen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumDepartment of Industrial and Operations Engineering, The University of Michigan, 48109, Ann Arbor, MI, USAen_US
dc.contributor.affiliationotherInstituto de Matematica Pura e Aplicada, 22460, Rio de Janeiro, Brazilen_US
dc.contributor.affiliationumcampusAnn Arboren_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/47914/1/10107_2005_Article_BF01580643.pdfen_US
dc.identifier.doihttp://dx.doi.org/10.1007/BF01580643en_US
dc.identifier.sourceMathematical Programmingen_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Show simple item record