@Misc{macau_mods_00001851, author = {Jansen, Klaus}, title = {Parameterized Approximation Scheme for the Multiple Knapsack Problem}, year = {1992}, publisher = {Institut f{\"u}r Informatik}, address = {Kiel}, volume = {0909}, abstract = {The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set {\$}A{\$} of {\$}n{\$} items and set {\$}B{\$} of {\$}m{\$} bins (knapsacks) such that each item {\$}a {\backslash}in A{\$} has a size {\$}size(a){\$} and a profit value {\$}profit(a){\$}, and each bin {\$}b {\backslash}in B{\$} has a capacity {\$}c(b){\$}. The goal is to find a subset {\$}U {\backslash}subset A{\$} of maximum total profit such that {\$}U{\$} can be packed into {\$}B{\$} without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit an FPTAS even if the number {\$}m{\$} of bins is two. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time {\$}n^{\{}O({\backslash}log(1/{\backslash}epsilon) / {\backslash}epsilon^8){\}}{\$}. In this paper we propose an EPTAS with parameterized running time {\$}2^{\{}O({\backslash}log(1/{\backslash}epsilon)/{\backslash}epsilon^5){\}} {\backslash}cdot poly(n) + O(m){\$} for MKP. This solves also an open question by Chekuri and Khanna.}, issn = {2192-6247}, url = {https://macau.uni-kiel.de/receive/macau_mods_00001851}, file = {:https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00002986/tr-0909-bericht.pdf:PDF}, language = {en} }