Packing groups of items into multiple knapsacks

Lin Chen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items which are partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be. Deciding if a group of items of total weight 2 could be packed into two knapsacks of unit capacity is already NP-hard and it thus rules out a constantapproximation algorithm for this problem in general. We then focus on the parameterized version where the total weight of items in each group is bounded by a factor δ of the total capacity of all knapsacks. Both approximation and inapproximability results with respect to δ are derived. We also show that, depending on whether the number of knapsacks is a constant or part of the input, the approximation ratio for the problem, as a function on δ, changes substantially, which has a clear difference from the classical multiple knapsack problem.

Original languageEnglish
Title of host publication33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
EditorsHeribert Vollmer, Nicolas Ollinger
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770019
DOIs
StatePublished - Feb 1 2016
Event33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 - Orleans, France
Duration: Feb 17 2016Feb 20 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume47
ISSN (Print)1868-8969

Conference

Conference33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
CountryFrance
CityOrleans
Period02/17/1602/20/16

Keywords

  • Approximation algorithms
  • Bin packing
  • Lower bound
  • Multiple knapsack

Fingerprint Dive into the research topics of 'Packing groups of items into multiple knapsacks'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., & Zhang, G. (2016). Packing groups of items into multiple knapsacks. In H. Vollmer, & N. Ollinger (Eds.), 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 [28] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 47). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2016.28