A fast asymptotic approximation scheme for bin packing with rejection

“Bin packing with rejection” is the following problem: 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. We show that bin packing with rejection can be reduced to n multiple knapsack problems and, based on techniques for the multiple knapsack problem, we give a fast asymptotic polynomial time approximation scheme,“Reject&Pack”, with time complexity O(nO(ϵ−2)). This improves a recent approximation scheme given by Epstein, which has time complexity O(nO((ϵ−4)ϵ−1)). We also show that Reject&Pack can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme.