Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Epstein, Leah
Levin, Asaf
van Stee, Rob

dblp
dblp
dblp

Not MPG Author(s):

Epstein, Leah
Levin, Asaf

BibTeX cite key*:

EpLeSt12

Title

Title*:

Approximation Schemes for Packing Splittable Items with Cardinality Constraints


cards-j_revised2.dvi (127.14 KB)

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://www.springer.com/computer/theoretical+computer+science/journal/453

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

62

Number:

1-2

Publishing Date:

February 2012

Pages*:

102-129

Number of
VG Pages:

28

Page Start:

201

Page End:

129

Sequence Number:


DOI:

10.1007/s00453-010-9445-6

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We continue the study of bin packing with splittable items and
cardinality constraints. In this problem, a set of $n$ 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 given parameter. Complicating the problem further is the fact
that items may be larger than 1, which is the size of a bin. The
problem is known to be strongly NP-hard for any fixed value of
$k$.

We essentially close this problem by providing an efficient
polynomial-time approximation scheme (EPTAS) for most of its
versions. Namely, we present an efficient polynomial time
approximation scheme for %values of $k$ such that
$k=o(n)$. A
PTAS for $k=\Theta (n)$ does not exist unless P $=$ NP.

Additionally, we present \emph{dual} approximation schemes for
$k=2$ and for constant values of $k$. Thus we show that for any
$\eps>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+\eps$.

URL for the Abstract:

http://www.mpi-inf.mpg.de/~vanstee/cards-j.pdf

Categories,
Keywords:

approximation algorithms, bin packing

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{EpLeSt12,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
TITLE = {Approximation Schemes for Packing Splittable Items with Cardinality Constraints},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {1-2},
VOLUME = {62},
PAGES = {102--129},
ADDRESS = {New York},
MONTH = {February},
ISBN = {0178-4617},
DOI = {10.1007/s00453-010-9445-6},
}


Entry last modified by Stephanie Müller, 12/06/2013
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)
[Library]
Created
12/09/2010 03:20:53 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Stephanie Müller
Anja Becker
Rob van Stee
Rob van Stee
Rob van Stee
Edit Dates
06.12.2013 13:19:13
01.02.2013 11:59:19
11/14/2012 11:28:02 AM
12/12/2011 04:05:39 PM
03/03/2011 05:57:43 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
cards-j_revised2.dvi