Statistical Methods in Algorithm Design and Analysis.
Abstract
The use of statistical methods in the design and analysis of discrete algorithms is explored. Among the design tools are randomization, ranking, sampling and subsampling, density estimation, and 'cell' or 'bucket' techniques. The analysis techniques include those based on the design methods as well as the use of stochastic convergence concepts and order statistics. The introductory chapter contains a literature survey and background material on probability theory. In Chapter 2, probabilistic approximation algorithms are discussed with the goal of exposing and correcting some oversights in previous work. Some advantages of the proposed solution to the problems encountered are the introduction of a model for dealing with random problems, and a set of methods for analyzing the probabilistic behavior of approximation algorithms which permit consideration of fairly complex algorithms in which there are dependencies among the random variables in question. Chapter 3 contains many useful design and analysis tools such as those mentioned above, and several examples of the uses of the methods. Algorithms which run in linear expected time for a wide range of probabilistic assumptions about their inputs are given for problems ranging from sorting to finding all nearest neighbors in a point set in k dimensions. Empirical results are presented which indicate that the sorting algorithm, Binsort, is a good alternative to Quicksort under most conditions. Finally, Chapter 4 describes the uses of results from order statistics to analyze greedy algorithms and to investigate the behavior of parallel algorithms. Among the results reported here are general theorems regarding the distribution of solution values for optimization problems on weighted graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1978
- Accession Number
- ADA061150
Entities
People
- Bruce W. Weide
Organizations
- Carnegie Mellon University