English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Improved Results for a Memory Allocation Problem

Epstein, L., & van Stee, R. (2011). Improved Results for a Memory Allocation Problem. Theory of Computing Systems, 48(1), 79-92. doi:10.1007/s00224-009-9226-2.

Item is

Files

show Files
hide Files
:
splitemj9.pdf (Any fulltext), 115KB
 
File Permalink:
-
Name:
splitemj9.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
© The Author(s) 2009
License:
-

Locators

show

Creators

show
hide
 Creators:
Epstein, Leah1, Author
van Stee, Rob2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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$.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 618646
DOI: 10.1007/s00224-009-9226-2
URI: http://dx.doi.org/10.1007/s00224-009-9226-2
Other: Local-ID: C1256428004B93B8-D4285FA8B979BEB2C12577F4004E594F-EpsSte11
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Theory of Computing Systems
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: New York, NY : Springer
Pages: - Volume / Issue: 48 (1) Sequence Number: - Start / End Page: 79 - 92 Identifier: ISSN: 1432-4350