Premium
Multiple subset sum with inclusive assignment set restrictions
Author(s) -
Kellerer Hans,
Leung Joseph Y.T.,
Li ChungLun
Publication year - 2011
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20466
Subject(s) - set (abstract data type) , set cover problem , computer science , subset sum problem , set packing , mathematics , frequency assignment , mathematical optimization , knapsack problem , programming language , telecommunications
In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492‐approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011