The expected number of extreme points of a random linear program (Q4726040)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3999651
Language Label Description Also known as
default for all languages
No label defined
    English
    The expected number of extreme points of a random linear program
    scientific article; zbMATH DE number 3999651

      Statements

      The expected number of extreme points of a random linear program (English)
      0 references
      0 references
      0 references
      1986
      0 references
      random linear program
      0 references
      random polytope
      0 references
      extreme points
      0 references
      average case algorithmic performance measures
      0 references
      There 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.
      0 references

      Identifiers