A ¾-approximation algorithm for multiple subset sum

A ¾-approximation algorithm for multiple subset sum

0.00 Avg rating0 Votes
Article ID: iaor20042352
Country: Netherlands
Volume: 9
Issue: 2
Start Page Number: 99
End Page Number: 111
Publication Date: Mar 2003
Journal: Journal of Heuristics
Authors:
Keywords: programming: mathematical
Abstract:

The Multiple Subset Sum Problem is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations. However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time ¾-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The ‘core’ of the algorithm is a procedure to pack triples of ‘large’ items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.

Reviews

Required fields are marked *. Your email address will not be published.