Joint performance of greedy heuristics for the integer knapsack problem (Q1343153)

The authors consider an integer knapsack problem with values \(v(i)\), weights \(w(i)\) and capacity \(W\). Their goal is to analyse composite algorithms which compute the best heuristic solution obtained from subsequent applications of greedy algorithms with different selection rules. Four of these rules are considered which are based on sorting the items by (1) increasing weight, (2) decreasing value, (3) decreasing density \(v(i)/w(i)\), and (4) decreasing total value \([W/w(i)] v(i)\). The authors prove that in the worst case a composite of the density- ordered and total-value ordered greedy algorithm is superior to all other combinations of greedy heuristics.