M.Sc Student | Yehezkely Omer |
---|---|

Subject | Approximation Schemes for Packing with Item Fragmentation |

Department | Department of Computer Science |

Supervisor | Professor Hadas Shachnai |

Full Thesis text |

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.