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

Distribution Statement:

APPROVED FOR PUBLIC RELEASE