# Accession Number:

## AD0743129

# Title:

## Estimates and Bounds on Computational Effort in the Accelerated and Bound-and-Scan Algorithm

# Descriptive Note:

## Technical rept.

# Corporate Author:

## STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH

# Personal Author(s):

# Report Date:

## 1972-05-15

# Pagination or Media Count:

## 41.0

# Abstract:

Methods for obtaining estimates and bounds on computational effort in the Accelerated bound-and-scan algorithm are presented. The basic tools of analysis used are various results from the theory of partitions of numbers, and central-limit theorem, and geometric interpretations of the algorithm. The results of the analysis are used to provide partial answers to questions such as a What is the greatest amount of time the algorithm could require to solve a given problem. b What is the expected computation time. c How should the variables and constraints be ordered. d How does the computation time depend on the number of variables. and E How is the computation time affected by the quality of the starting solution.

# Subject Categories:

- Operations Research