AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In this talk 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. Chekuri and Khanna (SODA 2000) 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 (SODA 2009) 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)$.

Rolf Harren

--email hidden

passcode not visible

logged in users only