Multiple subset sum with inclusive assignment set restrictions

Hans Kellerer, Joseph Y T Leung, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)


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
Pages (from-to)546-563
Number of pages18
JournalNaval Research Logistics
Issue number6
Publication statusPublished - 1 Sept 2011


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

ASJC Scopus subject areas

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


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

Cite this