Probabilistic analysis of optimization algorithms-some aspects from a practical point of view

In this paper the utility and the difficulties of probabilistic analysis for optimization algorithms are discussed. Such an analysis is expected to deliver valuable criteria-better than the worst-case complexity-for the efficiency of an algorithm in practice. The author has done much work of that kind in the field of linear programming. Based on that experience he gives some insight into the general principles for such an approach. He reports on some typical and representative attempts to analyze algorithms, resp. problems, of linear and combinatorial optimization. For each case he describes the problem, the stochastic model under consideration, the algorithm, the results, and tries to give a brief idea of the way these results could be obtained. He concludes with a discussion of some drawbacks and difficulties in that field of research. Among these are the strong sensibility with respect to the chosen model, the restriction of results to the asymptotic case, the restriction to somehow inefficient algorithms, etc. These points are the reasons why probabilistic analysis is of limited value for practice today. On the other hand, they show which principal problems should be attacked in the future to obtain the desired utility.