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 Goto entry point

 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 Attachment(s): 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: (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
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
Attachment Section

View attachments here: