Accession Number : AD0779438

Title :   When the Greedy Solution Solves a Class of Knapsack Problems.

Descriptive Note : Technical summary rept.,

Corporate Author : WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s) : Magazine,M. J. ; Nemhauser,G. L. ; Trotter,L. E. , Jr

Report Date : APR 1974

Pagination or Media Count : 27

Abstract : A heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal cost as large as possible is studied. Recursive necessary and sufficient conditions for the optimality of such greedy solutions and a good algorithm for verifying these conditions are given. Maximum absolute error for non-optimal greedy solutions is also examined. (Author)

Descriptors :   *INTEGER PROGRAMMING, RECURSIVE FUNCTIONS, MATHEMATICAL MODELS, DYNAMIC PROGRAMMING, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE