Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/14672
Title: Multiple subset sum with inclusive assignment set restrictions
Authors: Kellerer, H
Leung, JYT
Li, CL 
Keywords: Inclusive assignment sets
Polynomial time approximation scheme
Subset sum
Worst case analysis
Issue Date: 2011
Publisher: John Wiley & Sons
Source: Naval research logistics, 2011, v. 58, no. 6, p. 546-563 How to cite?
Journal: Naval research logistics 
Abstract: 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.
URI: http://hdl.handle.net/10397/14672
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20466
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
Citations as of Sep 23, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Sep 23, 2017

Page view(s)

46
Last Week
2
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.