Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2022) | last year (2021) | two years ago (2020) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Epstein, Leah van Stee, Rob dblp dblp Not MPG Author(s): Epstein, Leah
 BibTeX cite key*: EpsSte11

 Title
 Title*: Improved results for a memory allocation problem Attachment(s): splitemj9.pdf (114.86 KB)

 Journal
 Journal Title*: Theory of Computing Systems Journal's URL: http://www.springer.com/computer/theoretical+comput+erscience/journal/224 Download URL for the article: http://dx.doi.org/10.1007/s00224-009-9226-2 Language: English

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer-ny.com/ Publisher's Address: New York, NY ISSN: 1432-4350

 Vol, No, pp, Date
 Volume*: 48 Number: 1 Publishing Date: January 2011 Pages*: 79-92 Number of VG Pages: 14 Page Start: 79 Page End: 92 Sequence Number: DOI: 10.1007/s00224-009-9226-2

 Note: (LaTeX) Abstract: We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. This problem was recently introduced by Chung et al.~\cite{ChGrVM06}. We give a simple $\frac 32$-approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most $k$ parts of items. We show that this general case is strongly NP-hard for any $k \geq 3$. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily close to $\frac 75$. URL for the Abstract: http://www.mpi-inf.mpg.de/~vanstee/splitemj9.pdf Categories, Keywords: online algorithms, bin packing, approximation algorithms HyperLinks / References / URLs: Copyright Message: © The Author(s) 2009 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{EpsSte11,
AUTHOR = {Epstein, Leah and van Stee, Rob},
TITLE = {Improved results for a memory allocation problem},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2011},
NUMBER = {1},
VOLUME = {48},
PAGES = {79--92},