The expected number of extreme points of a random linear program

DOI10.1007/BF01580643zbMath0616.90041OpenAlexW1972413660MaRDI QIDQ4726040

Sancho E. Berenguer, Robert L. Smith

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580643

zbMATH Keywords

extreme pointsrandom polytopeaverage case algorithmic performance measuresrandom linear program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Cites Work

• Computational results on an algorithm for finding all vertices of a polytope
• Random polytopes: Their definition, generation and aggregate properties
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• The Probability that a Random Polytope is Bounded
• The convex hull of a random set of points
• Partitions ofN-Space by Hyperplanes
• The maximum numbers of faces of a convex polytope
• Partition of Space

This page was built for publication: The expected number of extreme points of a random linear program