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
van Stee, Rob

dblp
dblp

Not MPG Author(s):

Epstein, Leah

BibTeX cite key*:

EpsSte11

Title

Title*:

Improved results for a memory allocation problem


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
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:15:46 PM
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

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

View attachments here:


File Attachment Icon
splitemj9.pdf