An Improved Approximation Scheme for Variable-Sized Bin Packing

摘要

The Variable-Sized Bin Packing Problem (abbreviated as VSBPP or VBP) is a well-known generalization of the NP-hard Bin Packing Problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an asymptotic approximation scheme (AFPTAS) for VBP and BP with performance guarantee A(epsilon)(I) <= (1 + epsilon) OPT (I) + O(log(2)(1/epsilon)) for any problem instance I and any epsilon > 0. The additive term is much smaller than the additive term of already known AFPTAS. The running time of the algorithm is O (1/epsilon(6)log(1/epsilon) + (log(1/epsilon)n)for BP and O (1/epsilon(6)log(2)(1/epsilon) + M + log(1/epsilon)n) for VBP, which is an improvement to previously known algorithms. Many approximation algorithms have to solve subproblems, for example instances of the Knapsack Problem (KP) or one of its variants. These subproblems - like KP - are in many cases NP-hard. Our AFPTAS for VBP must in fact solve a generalization of KP, the Knapsack Problem with Inversely Proportional Profits (KPIP). In this problem, one of several knapsack sizes has to be chosen. At the same time, the item profits are inversely proportional to the chosen knapsack size so that the largest knapsack in general does not yield the largest profit. We introduce KPIP in this paper and develop an approximation scheme for KPIP by extending Lawler's algorithm for KP. Thus, we are able to improve the running time of our AFPTAS for VBP.