@Misc{macau_mods_00001844,
  author = 	{Jansen, Klaus},
  title = 	{A fast approximation scheme for the multiple knapsack problem},
  year = 	{1992},
  publisher = 	{Institut f{\"u}r Informatik},
  address = 	{Kiel},
  volume = 	{0916},
  abstract = 	{In this paper we propose an improved efficient approximation scheme for the multiple knapsack problem (MKP). Given a set {\$}A{\$} of {\$}n{\$} items and set {\$}B{\$} of {\$}m{\$} bins with possibly different capacities, the goal is to find a subset {\$}A'/ {\backslash}subseteq A{\$} of maximum total profit that can be packed into {\$}B{\$} without exceeding the capacities of the bins. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with arbitrary capacities with running time {\$}n^{\{}O(1/ {\backslash}epsilon^8 {\backslash}log(1/{\backslash}epsilon)){\}}{\$}. Recently we found an EPTAS for MKP with running time {\$}2^{\{}O(1/{\backslash}epsilon^5 {\backslash}log(1/{\backslash}epsilon)){\}} poly(n){\$}. Here we present an improved EPTAS with running time {\$}2^{\{}O(1/{\backslash}epsilon {\backslash}log(1/{\backslash}epsilon)^4){\}} poly(n){\$}. If the modified round-up property for bin packing with different sizes is true, the running time can be improved to {\$}2^{\{}O(1/{\backslash}epsilon {\backslash}log(1/{\backslash}epsilon)^2){\}} poly(n){\$}.},
  issn = 	{2192-6247},
  url = 	{https://macau.uni-kiel.de/receive/macau_mods_00001844},
  file = 	{:https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00002993/tr-0916-bericht.pdf:PDF},
  language = 	{en}
}