Heuristic and reduction algorithms for the knapsack sharing problem

The knapsack sharing problem (KSP) is newly formulated as an extension of the knapsack problem. KSP is NP-hard, and we give a fast algorithm to find an upper bound to this problem. Based on this we develop a heuristic algorithm to solve KSP approximately. Also, a pegging test is derived that enables us to reduce the size of the original problem. Computational experiments are carried out to examine the behavior of the developed algorithms for several instance types of different statistical characteristics.