A fast approximation scheme for the multiple knapsack problem

zum Volltext (390 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juli 2009
Seitenbereich33 S.

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)$.
BemerkungAnnotation :
  • 2. Version am 15.02.2010
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000089
 
URN:NBNurn:nbn:de:101:1-201203133385
IDNummer des Berichts :
  • TR_0916