AN ADDENDUM TO “SOME THOUGHTS ON THE 2-APPROXIMATION ALGORITHM FOR KNAPSACK PROBLEMS: A SURVEY”
As above, this is an addendum to (Iida [1]), which treats 14 types of knapsack problem relating to the conventional 2-approximation algorithm for the 0-1 knapsack problem. The addendum includes two topics:first,wehavehereincollectedthree2-approximation algorithms for the 0-1 knapsack problem proposed to date; second, amongst the three, on the first and the simplest one, we show that it ends in failure to apply the simplest to the set-union knapsack problem, and also show a condition under which the simplest works for the multiple knapsack problem.
combinatorial optimization, knapsack problem, 2-approximation algorithm, greedy.