Average-case analysis for combinatorial problems.

摘要

This thesis considers the average case analysis of algorithms, focusing primarily on NP-hard combinatorial optimization problems. It includes a catalog of distributions frequently used in average-case analysis and a collection of mathematical tools that have been useful in studying these distributions. The bulk of the thesis consists of case-studies in average-case analysis of algorithms. Algorithms for 3-SAT, Subset Sum, Strong Connectivity, Stochastic Minimum Spanning Tree, and Uncapacitated Facility Location are analyzed on random instances.