Multiple subset sum with inclusive assignment set restrictions

Hans Kellerer, Joseph Y.T. Leung, Chung Lun Li

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)546-563
Number of pages18
JournalNaval Research Logistics
Volume58
Issue number6
DOIs
StatePublished - Sep 1 2011

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Keywords

  • inclusive assignment sets
  • polynomial time approximation scheme
  • subset sum
  • worst case analysis

Fingerprint Dive into the research topics of 'Multiple subset sum with inclusive assignment set restrictions'. Together they form a unique fingerprint.

Cite this