Re: Greedy Algorithm




Googmeister wrote:

Here's a reference to a proof.

TI : Optimality of a Heuristic Solution for a Class of Knapsack
Problems
AU : Hu, T. C.; Lenard, M. L.
VO : 24
NO : 1
DA : Jan. - Feb., 1976
PP : 193-196
AB : This paper presents a simpler proof for a result of Magazine,
Nemhauser, and Trotter, which states recursive necessary and sufficient
conditions for the optimality of a heuristic solution for a class of
knapsack problems.

...where the journal is presumably "Operations Research".

Mitch

.