Technical Report MSC-2007-06

TR#:MSC-2007-06
Class:MSC
Title: Approximation Schemes for Packing with Item Fragmentation
Authors: Omer Yehezkely
Supervisors: Hadas Shachnai
PDFMSC-2007-06.pdf
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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2007/MSC/MSC-2007-06), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2007
To the main CS technical reports page

Computer science department, Technion