Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs

摘要

Motivated from recent applications in community TV networks and VLSI circuit design, we study variants of the classic bin packing problem, in which a set of items needs to be packed in a minimum number of unit-sized bins, allowing items to be fragmented. This can potentially reduce the total number of bins used, however, item fragmentation does not come for free. In bin packing with size preserving fragmentation (BP-SPF), there is a bound on the total number of fragmented items. In bin packing with size increasing fragmentation (BP-SIF), fragmenting an item increases the input size (due to a header/footer of fixed size that is added to each fragment). Both BP-SPF and BP-SIF do not belong to the class of problems that admit a polynomial time approximation scheme (PTAS). In this paper, we develop fast asymptotic fully polynomial time approximation schemes (AFPTAS) for both problems. The running times of our schemes are linear in the input size. As special cases, our schemes yield AFPTASs for classical bin packing and for variable-sized bin packing, whose running times improve the best known running times for these problems.