Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM DYNAMIC STORAGE ALLOCATION

• INSTANCE: Set A of items to be stored, each $a\in A$ having a size $s(a)\in Z^+$, an arrival time $r(a) \in Z^{+}$, and a departure time $d(a) \in Z^{+}$.

• SOLUTION: A feasible allocation of storage for A, i.e., a function $\sigma: A \rightarrow Z^{+}$ such that, for all $a,a' \in A$, if $I(a) \cap I(a')$ is nonempty then either $d(a) \leq r(a')$ or $d(a') \leq r(a)$.

• MEASURE: The size of the allocation, i.e., $\max_{a \in A}(\sigma(a)+s(a)-1)$.

  
  

• Good News: Approximable within 5 [192].

• Comment: Approximable within 5/2 if the sizes are powers of 2 and within 2 if only two sizes are allowed [192].