Approximation Schemes for Packing with Item Fragmentation.
Saved in:
| Title: | Approximation Schemes for Packing with Item Fragmentation. |
|---|---|
| Authors: | Shachnai, Hadas1 hadas@cs.technion.ac.il, Tamir, Tami2 tami@idc.ac.il, Yehezkely, Omer1 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 31315240 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Approximation Schemes for Packing with Item Fragmentation. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Shachnai%2C+Hadas%22">Shachnai, Hadas</searchLink><relatesTo>1</relatesTo><i> hadas@cs.technion.ac.il</i><br /><searchLink fieldCode="AR" term="%22Tamir%2C+Tami%22">Tamir, Tami</searchLink><relatesTo>2</relatesTo><i> tami@idc.ac.il</i><br /><searchLink fieldCode="AR" term="%22Yehezkely%2C+Omer%22">Yehezkely, Omer</searchLink><relatesTo>1</relatesTo><i> omery@cs.technion.ac.il</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Jul2008, Vol. 43 Issue 1, p81-98. 18p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Storage+fragmentation+%28Computer+science%29%22">Storage fragmentation (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Bins%22">Bins</searchLink><br /><searchLink fieldCode="DE" term="%22Materials+handling%22">Materials handling</searchLink><br /><searchLink fieldCode="DE" term="%22Television+networks%22">Television networks</searchLink><br /><searchLink fieldCode="DE" term="%22Stores+or+stock-room+keeping%22">Stores or stock-room keeping</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+programming%22">Linear programming</searchLink><br /><searchLink fieldCode="DE" term="%22Asymptotic+expansions%22">Asymptotic expansions</searchLink><br /><searchLink fieldCode="DE" term="%22Stochastic+convergence%22">Stochastic convergence</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink><br /><searchLink fieldCode="DE" term="%22Television+transmitters+%26+transmission%22">Television transmitters & transmission</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=31315240 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-007-9082-x Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 18 StartPage: 81 Subjects: – SubjectFull: Storage fragmentation (Computer science) Type: general – SubjectFull: Bins Type: general – SubjectFull: Materials handling Type: general – SubjectFull: Television networks Type: general – SubjectFull: Stores or stock-room keeping Type: general – SubjectFull: Linear programming Type: general – SubjectFull: Asymptotic expansions Type: general – SubjectFull: Stochastic convergence Type: general – SubjectFull: Approximation theory Type: general – SubjectFull: Television transmitters & transmission Type: general Titles: – TitleFull: Approximation Schemes for Packing with Item Fragmentation. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Shachnai, Hadas – PersonEntity: Name: NameFull: Tamir, Tami – PersonEntity: Name: NameFull: Yehezkely, Omer IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2008 Type: published Y: 2008 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 43 – Type: issue Value: 1 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
