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