A fast approximation scheme for the multiple knapsack problem

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)$.

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.