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
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
0.8604913
0 references
0.8473306
0 references
0.8441296
0 references
0.84099674
0 references
0.8409798
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