@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}
}