An Improved Approximation Scheme for Variable-Sized Bin Packing.
Saved in:
| Title: | An Improved Approximation Scheme for Variable-Sized Bin Packing. |
|---|---|
| Authors: | Jansen, Klaus1 kj@informatik.uni-kiel.de, Kraft, Stefan1 stkr@informatik.uni-kiel.de |
| Source: | Theory of Computing Systems. Aug2016, Vol. 59 Issue 2, p262-322. 61p. |
| Subjects: | Approximation theory, Scheme programming language, Mathematical variables, Bin packing problem, NP-hard problems |
| Abstract: | The Variable-Sized Bin Packing Problem (abbreviated as VSBPP or VBP) is a well-known generalization of the NP-hard Bin Packing Problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an asymptotic approximation scheme (AFPTAS) for VBP and BP with performance guarantee $A_{\varepsilon }(I) \leq (1+ \varepsilon )OPT(I) + \mathcal {O}\left ({\log ^{2}\left (\frac {1}{\varepsilon }\right )}\right )$ for any problem instance I and any ε>0. The additive term is much smaller than the additive term of already known AFPTAS. The running time of the algorithm is $\mathcal {O}\left ({ \frac {1}{\varepsilon ^{6}} \log \left ({\frac {1}{\varepsilon }}\right ) + \log \left ({\frac {1}{\varepsilon }}\right ) n}\right )$ for BP and $\mathcal {O}\left ({ \frac {1}{{\varepsilon }^{6}} \log ^{2}\left ({\frac {1}{\varepsilon }}\right ) + M + \log \left ({\frac {1}{\varepsilon }}\right )n}\right )$ for VBP, which is an improvement to previously known algorithms. Many approximation algorithms have to solve subproblems, for example instances of the Knapsack Problem (KP) or one of its variants. These subproblems - like KP - are in many cases NP-hard. Our AFPTAS for VBP must in fact solve a generalization of KP, the Knapsack Problem with Inversely Proportional Profits (KPIP). In this problem, one of several knapsack sizes has to be chosen. At the same time, the item profits are inversely proportional to the chosen knapsack size so that the largest knapsack in general does not yield the largest profit. We introduce KPIP in this paper and develop an approximation scheme for KPIP by extending Lawler's algorithm for KP. Thus, we are able to improve the running time of our AFPTAS for VBP. [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: 116790635 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: An Improved Approximation Scheme for Variable-Sized Bin Packing. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Jansen%2C+Klaus%22">Jansen, Klaus</searchLink><relatesTo>1</relatesTo><i> kj@informatik.uni-kiel.de</i><br /><searchLink fieldCode="AR" term="%22Kraft%2C+Stefan%22">Kraft, Stefan</searchLink><relatesTo>1</relatesTo><i> stkr@informatik.uni-kiel.de</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Aug2016, Vol. 59 Issue 2, p262-322. 61p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink><br /><searchLink fieldCode="DE" term="%22Scheme+programming+language%22">Scheme programming language</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+variables%22">Mathematical variables</searchLink><br /><searchLink fieldCode="DE" term="%22Bin+packing+problem%22">Bin packing problem</searchLink><br /><searchLink fieldCode="DE" term="%22NP-hard+problems%22">NP-hard problems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The Variable-Sized Bin Packing Problem (abbreviated as VSBPP or VBP) is a well-known generalization of the NP-hard Bin Packing Problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an asymptotic approximation scheme (AFPTAS) for VBP and BP with performance guarantee $A_{\varepsilon }(I) \leq (1+ \varepsilon )OPT(I) + \mathcal {O}\left ({\log ^{2}\left (\frac {1}{\varepsilon }\right )}\right )$ for any problem instance I and any ε>0. The additive term is much smaller than the additive term of already known AFPTAS. The running time of the algorithm is $\mathcal {O}\left ({ \frac {1}{\varepsilon ^{6}} \log \left ({\frac {1}{\varepsilon }}\right ) + \log \left ({\frac {1}{\varepsilon }}\right ) n}\right )$ for BP and $\mathcal {O}\left ({ \frac {1}{{\varepsilon }^{6}} \log ^{2}\left ({\frac {1}{\varepsilon }}\right ) + M + \log \left ({\frac {1}{\varepsilon }}\right )n}\right )$ for VBP, which is an improvement to previously known algorithms. Many approximation algorithms have to solve subproblems, for example instances of the Knapsack Problem (KP) or one of its variants. These subproblems - like KP - are in many cases NP-hard. Our AFPTAS for VBP must in fact solve a generalization of KP, the Knapsack Problem with Inversely Proportional Profits (KPIP). In this problem, one of several knapsack sizes has to be chosen. At the same time, the item profits are inversely proportional to the chosen knapsack size so that the largest knapsack in general does not yield the largest profit. We introduce KPIP in this paper and develop an approximation scheme for KPIP by extending Lawler's algorithm for KP. Thus, we are able to improve the running time of our AFPTAS for VBP. [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=116790635 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-015-9644-2 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 61 StartPage: 262 Subjects: – SubjectFull: Approximation theory Type: general – SubjectFull: Scheme programming language Type: general – SubjectFull: Mathematical variables Type: general – SubjectFull: Bin packing problem Type: general – SubjectFull: NP-hard problems Type: general Titles: – TitleFull: An Improved Approximation Scheme for Variable-Sized Bin Packing. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Jansen, Klaus – PersonEntity: Name: NameFull: Kraft, Stefan IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: Aug2016 Type: published Y: 2016 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 59 – Type: issue Value: 2 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
