Note: On the set-union knapsack problem

The authors consider a generalization of the 0-1 knapsack problem called the set-union knapsack problem (SKP). In the SKP, each item is a set of elements, each item has a nonnegative value, and each element has a nonnegative weight. The total weight of a collection of items is given by the total weight of the elements in the union of the items’ sets. This problem has applications to data-base partitioning and to machine loading in flexible manufacturing systems. The authors show that the SKP remains NP-hard, even in very restricted cases. They present an exact, dynamic programming algorithm for the SKP and show sufficient conditions for it to run in polynomial time.