Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Author(s): Epstein, Leah van Stee, Rob dblp dblp Not MPG Author(s): Epstein, Leah
 Editor(s): Kaklamanis, Christos Skutella, Martin dblp dblp Not MPII Editor(s): Kaklamanis, Christos Skutella, Martin
 BibTeX cite key*: vanStee2008j
 Title, Booktitle
 Title*: Approximation schemes for packing splittable items with cardinality constraints cards-j.ps (59.9 KB) Booktitle*: Approximation and Online Algorithms, 5th International Workshop, WAOA 2007
 Event, URLs
 Conference URL:: http://www.algo07.cs.tau.ac.il/waoa.html Downloading URL: http://www.springerlink.com/content/t27t314840n32521/fulltext.pdf Event Address*: Eilat, Israel Language: English Event Date* (no longer used): Organization: Event Start Date: 11 October 2007 Event End Date: 12 October 2007
 Publisher
 Name*: Springer URL: http://www.springer-ny.com/ Address*: Berlin Type:
 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 4927 Number: Month: February Pages: 232-245 Year*: 2008 VG Wort Pages: 14 ISBN/ISSN: 0302-9743 Sequence Number: DOI: 10.1007/978-3-540-77918-6
 (LaTeX) 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$. Keywords: bin packing, approximation algorithms Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{vanStee2008j,
AUTHOR = {Epstein, Leah and van Stee, Rob},
EDITOR = {Kaklamanis, Christos and Skutella, Martin},
TITLE = {Approximation schemes for packing splittable items with cardinality constraints},
BOOKTITLE = {Approximation and Online Algorithms, 5th International Workshop, WAOA 2007},
PUBLISHER = {Springer},
YEAR = {2008},
VOLUME = {4927},
PAGES = {232--245},
SERIES = {Lecture Notes in Computer Science},