English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Approximation Schemes for Packing Splittable Items with Cardinality Constraints

Epstein, L., & van Stee, R. (2008). Approximation Schemes for Packing Splittable Items with Cardinality Constraints. In C. Kaklamanis, & M. Skutella (Eds.), Approximation and Online Algorithms (pp. 232-245). Berlin: Springer. doi:10.1007/978-3-540-77918-6.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1B0B-E Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-F333-8
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Epstein, Leah1, Author
van Stee, Rob2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of items must be packed into as few bins as possible. Items may be split, but each bin may contain at most $k$ (parts of) items, where $k$ is some fixed constant. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. We close this problem by providing a polynomial-time approximation scheme for it. We first present a scheme for the case $k=2$ and then for the general case of constant $k$. Additionally, we present \emph{dual} approximation schemes for $k=2$ and constant $k$. Thus we show that for any $\varepsilon>0$, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size $1+\varepsilon$.

Details

show
hide
Language(s): eng - English
 Dates: 2009-03-0320082008
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 428065
DOI: 10.1007/978-3-540-77918-6
URI: http://www.springerlink.com/content/t27t314840n32521/fulltext.pdf
Other: Local-ID: C125756E0038A185-4BF479C08756F3CBC125753C0045AA08-vanStee2008j
 Degree: -

Event

show
hide
Title: 5th International Workshop on Approximation and Online Algorithms
Place of Event: Eilat, Israel
Start-/End Date: 2007-10-11 - 2007-10-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Approximation and Online Algorithms
  Abbreviation : WAOA 2007
  Subtitle : 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers
Source Genre: Proceedings
 Creator(s):
Kaklamanis, Christos1, Editor
Skutella, Martin2, Editor           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 232 - 245 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4927 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743