When the Greedy Solution Solves a Class of Knapsack Problems

M. J. Magazine, G. L. Nemhauser and L. E. Trotter
Additional contact information
M. J. Magazine: North Carolina State University, Raleigh, North Carolina
G. L. Nemhauser: Cornell University, Ithaca, New York
L. E. Trotter: Yale University, New Haven, Connecticut

Operations Research, 1975, vol. 23, issue 2, 207-217

Abstract: This paper analyzes a heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal unit cost as large as possible. 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 nonoptimal “greedy” solutions is also examined.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.2.207 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:23:y:1975:i:2:p:207-217

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().