A PTAS for the Multiple Subset Sum Problem with different knapsack capacities

Authors
Caprara, A Kellerer, H Pferschy, U
Citation
A. Caprara et al., A PTAS for the Multiple Subset Sum Problem with different knapsack capacities, INF PROCESS, 73(3-4), 2000, pp. 111-118
Citations number
5
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
73
Issue
3-4
Year of publication
2000
Pages
111 - 118
Database
ISI
SICI code
0020-0190(20000229)73:3-4<111:APFTMS>2.0.ZU;2-5
Abstract
We present a PTAS for the Multiple Subset Sum Problem (MSSP) with different knapsack capacities. This is the selection of items from a given ground se t and their assignment to a given number of knapsacks such that the sum of the item weights in every knapsack does not exceed its capacity and the tot al sum of the weights of the packed items is as large as possible. Our resu lt generalizes the PTAS for the special case in which all knapsack capaciti es are identical [1]. (C) 2000 Elsevier Science B.V. All rights reserved.