000K  utf8
1100  $c2009
1500  eng
2050  urn:nbn:de:101:1-201203133385
3000  Jansen, Klaus
4000  A fast approximation scheme for the multiple knapsack problem  [Jansen, Klaus]
4209  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'/ \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/ \epsilon^8 \log(1/\epsilon))}$. Recently we found an EPTAS for MKP with running time $2^{O(1/\epsilon^5 \log(1/\epsilon))} poly(n)$. Here we present an improved EPTAS with running time $2^{O(1/\epsilon \log(1/\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/\epsilon \log(1/\epsilon)^2)} poly(n)$.
4950  https://nbn-resolving.org/urn:nbn:de:101:1-201203133385$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/macau_mods_00001844
5051  004