Low order polynomial bounds on the expected performance of local improvement algorithms (Q4721084)

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 3993298
Language Label Description Also known as
default for all languages
No label defined
    English
    Low order polynomial bounds on the expected performance of local improvement algorithms
    scientific article; zbMATH DE number 3993298

      Statements

      Low order polynomial bounds on the expected performance of local improvement algorithms (English)
      0 references
      0 references
      1986
      0 references
      average performance of algorithms
      0 references
      extremal set theory
      0 references
      local improvement
      0 references
      principal pivoting
      0 references
      linear complementarity
      0 references
      hill climbing in artificial intelligence
      0 references
      We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en log n and \(en^ 2\) for different distributions, respectively, as well as polyomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references