When the Greedy Solution Solves a Class of Knapsack Problems.
Technical summary rept.,
WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
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
- Operations Research