Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.algo07.cs.tau.ac.il/waoa.html

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
cards-j.ps