Polynomial Local Improvement Algorithms in Combinatorial Optimization

摘要

The subject of this report is an analysis of the expected, or average case performance of local improvement algorithms. The first chapter presents the basic model, defines the combinatorial structures which are the basis for the analysis, and describes the randomness assumptions upon which the expectation are based. The second chapter examines these structures in more detail, including an analysis of both best and worst case performance. The third chapter discusses simulation results which predict an approximately linear average case performance, and proves an O(n2 log n) upper bound for two of the random distributions assumed. Chapter Four proves some extensions and sharper versions of this upper bound. The fifth chapter applies the model to principal pivoting algorithms for the linear complementarity problem, and to the simplex method. Although local improvement is not guaranteed to find a global optimum for all problems, most notably those that are NP-complete, it is nonetheless often used in these cases. Chapter Six discusses these appllications.