The Multiple Subset Sum Problem

In the {\em multiple subset sum problem} (MSSP) items from a given ground set are selected and packed into a given number of identical bins such that the sum of the item weights in every bin does not exceed the bin capacity and the total sum of the weights of the items packed is as large as possible...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2000, Vol.11 (2), p.308-319
Main Authors: Caprara, Alberto, Kellerer, Hans, Pferschy, Ulrich
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Knapsack problem
Linear programming
Marble
Optimization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the {\em multiple subset sum problem} (MSSP) items from a given ground set are selected and packed into a given number of identical bins such that the sum of the item weights in every bin does not exceed the bin capacity and the total sum of the weights of the items packed is as large as possible. This problem is a relevant special case of the multiple knapsack problem, for which the existence of a polynomial-time approximation scheme (PTAS) is an important open question in the field of knapsack problems. One main result of the present paper is the construction of a PTAS for MSSP. For the bottleneck case of the problem, where the minimum total weight contained in any bin is to be maximized, we describe a 2/3-approximation algorithm and show that this is the best possible approximation ratio. Moreover, PTASs are derived for the special cases in which either the number of bins or the number of different item weights is constant. We finally show that, even for the case of only two bins, no fully PTAS exists for both versions of the problem.
ISSN:1052-6234
1095-7189
DOI:10.1137/S1052623498348481