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

Report Date:

1974-04-01

Pagination or Media Count:

27.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE