A constant factor approximation algorithm for the storage allocation problem
Reuven Bar-Yehuda, Michael Beder, Dror Rawitz · 2013
We study the Storage Allocation Problem (SAP) which is a variant of the Unsplittable Flow Problem on Paths (UFPP). A SAP instance consists of a path P = (V,E) and a set J of tasks. Each edge e ∈ E has a capacity ce and each task j ∈ J is associated with a path Ij in P, a demand dj and a weight wj. The goal is to find a maximum weight subset S ⊆ J of tasks and a height function h:S → ℜ+ such that (i) h(j)|+dj ≤ ce, for every e ∈ Ij; and (ii) if j,i ∈ S such that Ij ∩ Ii ≠ ∅ and h(j) ≥ h(i), then h(j) ≥ h(i) + di. SAP can be seen as a rectangle packing problem in which rectangles can be moved vertically, but not horizontally.