Approximation Schemes for Packing with Item Fragmentation.

Saved in:

Bibliographic Details
Title:	Approximation Schemes for Packing with Item Fragmentation.
Authors:	Shachnai, Hadas¹ hadas@cs.technion.ac.il, Tamir, Tami² tami@idc.ac.il, Yehezkely, Omer¹ omery@cs.technion.ac.il
Source:	Theory of Computing Systems. Jul2008, Vol. 43 Issue 1, p81-98. 18p.
Subjects:	Storage fragmentation (Computer science), Bins, Materials handling, Television networks, Stores or stock-room keeping, Linear programming, Asymptotic expansions, Stochastic convergence, Approximation theory, Television transmitters & transmission
Abstract:	We consider two variants of the classical bin packing problem in which items may be fragmented. This can potentially reduce the total number of bins needed 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 in this paper that both problems admit a dual PTAS and an asymptotic PTAS. We also develop for each of the problems a dual asymptotic fully polynomial time approximation scheme ( AFPTAS). Our AFPTASs are based on a non-standard transformation of the mixed packing and covering linear program formulations of our problems into pure covering programs, which enables to efficiently solve these programs. [ABSTRACT FROM AUTHOR]
	Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	We consider two variants of the classical bin packing problem in which items may be fragmented. This can potentially reduce the total number of bins needed 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 in this paper that both problems admit a dual PTAS and an asymptotic PTAS. We also develop for each of the problems a dual asymptotic fully polynomial time approximation scheme ( AFPTAS). Our AFPTASs are based on a non-standard transformation of the mixed packing and covering linear program formulations of our problems into pure covering programs, which enables to efficiently solve these programs. [ABSTRACT FROM AUTHOR]
ISSN:	14324350
DOI:	10.1007/s00224-007-9082-x