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. This improves a recent approximation scheme given by Epstein, which has time complexity. 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.
展开▼
