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