| Abstract: | We 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. We show that the SKP remains NP-hard, even in very restricted cases. We present an exact, dynamic programming algorithm for the SKP and show sufficient conditions for it to run in polynomial time. © 1994 John Wiley & Sons, Inc. |
