MPI-INF D1 Publications: Journal Article: Improved results for a memory allocation problem

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

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, Abstract, ©

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},
ADDRESS = {New York, NY},
MONTH = {January},
ISBN = {1432-4350},
DOI = {10.1007/s00224-009-9226-2},
}

Entry last modified by Anja Becker, 02/09/2012

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 12/09/2010 15:15:46
Revisions 2. 1. 0.	Editor(s) Anja Becker Rob van Stee Rob van Stee	Edit Dates 09.02.2012 10:46:10 01-07-2011 11:55:05 12-09-2010 15:15:46

Attachment Section

splitemj9.pdf

splitemj9.pdf