M.Sc Thesis
M.Sc Student Yehezkely Omer Approximation Schemes for Packing with Item Fragmentation Department of Computer Science Professor Hadas Shachnai

Abstract

We consider two 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, and the items may be fragmented. This can potentially reduce the total number of bins used for packing the instance. However, since fragmentation incurs overhead, we attempt to avoid it as much as possible. 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). In bin packing with size preserving fragmentation (BP-SPF), there is a bound on the total number of fragmented items. These two variants of bin packing capture many practical scenarios, including message transmission in community TV networks, VLSI circuit design and preemptive scheduling on parallel machines with setup times/setup costs.

While both BP-SPF and BP-SIF do not belong to the class of problems that admit a polynomial time approximation scheme (PTAS), we show that both problems admit dual PTAS, asymptotic PTAS (APTAS), and asymptotic fully polynomial time approximation scheme (AFPTAS). In particular, given an instance I of BP-SPF, and ε>0, we develop

* A dual PTAS which packs the items in OPT(I) bins of sizes 1 + ε, where OPT(I) is the number of bins used by an optimal packing.

* An APTAS which packs the items using at most OPT(I)(1 + ε) + 1 unit-sized bins.

* A dual AFPTAS, which packs the items into OPT(I)+k unit-sized bins of size 1+ ε, where k ≤ 4/ ε 2 + 3.

* An AFPTAS whose running time is linear in n, the number of items in I, which packs the items into OPT(I) + k unit-sized bins, where k = O(ε -1 log ε -1).

We show that all of these schemes can be applied with slight changes to BP-SIF.

Our AFPTAS yields as a special case AFPTAS with improved running time for the classic bin packing problem.

In developing approximation schemes for packing with item fragmentation, we apply several techniques, which are of independent interest. This includes a non-standard transformation of mixed packing and covering linear programs into pure covering programs, and a novel oblivious version of the shifting technique, that is used for obtaining a fixed number of distinct fragment sizes in the instance.