TY - GEN

T1 - Packing groups of items into multiple knapsacks

AU - Chen, Lin

AU - Zhang, Guochuan

N1 - Funding Information:
Research supported in part by NSFC (11271325).
Publisher Copyright:
© Lin Chen and Guochuan Zhang; licensed under Creative Commons License CC-BY.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bin packing

KW - Lower bound

KW - Multiple knapsack

UR - http://www.scopus.com/inward/record.url?scp=84961659532&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2016.28

DO - 10.4230/LIPIcs.STACS.2016.28

M3 - Conference contribution

AN - SCOPUS:84961659532

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016

A2 - Vollmer, Heribert

A2 - Ollinger, Nicolas

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 17 February 2016 through 20 February 2016

ER -