A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection

摘要

The bin packing with rejection problem is the following: Given a list of items with associated sizes and rejection costs, find a packing into unit bins of a subset of the list, such that the number of bins used plus the sum of rejection costs of unpacked items is minimized. In this paper, we first show that bin packing with rejection can be reduced to n multiple knapsack problems. Then, based on techniques for the multiple knapsack problem we give a fast asymptotic polynomial time approximation scheme with time complexity O(n~(O(∈~(-2))). This improves a recent approximation scheme given by Epstein, which has timecomplexity O(n~(O((∈~(-4)∈~(-1))))). Finally, we show that our algorithm can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme for it.