MPI-INF Logo
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
Note, Abstract, ©
(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},
 ADDRESS = {Eilat, Israel},
 MONTH = {February},
 ISBN = {0302-9743},
 DOI = {10.1007/978-3-540-77918-6},
}

Entry last modified by Rob van Stee, 03/03/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rob van Stee		Created
01/12/2009 01:40:55 PM
Revision
0.



Editor
Rob van Stee



Edit Date
01/12/2009 01:40:55 PM



File Attachment Icon
cards-j.ps