# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Improved Results for a Memory Allocation Problem

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0010-123E-E

##### 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$.