A Constant Factor Approximation Algorithm for the Storage Allocation Problem

摘要

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 c_e and each task j ∈ J is associated with a path I_j in P, a demand d_j and a weight w_j. The goal is to find a maximum weight subset S is containd in J of tasks and a height function h : S → R~+ such that (ⅰ) h(j)+d_j ≤ c_e. for every e ∈ I_j; and (ⅱ) if j, i ∈ S such that I_j ∩ I_i ≠ 0 and h(j) ≥ h(i), then h(j) ≥ h(i) + d_i. SAP can be seen as a rectangle packing problem in which rectangles can be moved vertically, but not horizontally. We present a polynomial time (9 + ε)-approximation algorithm for SAP. Our algorithm is based on a variation of the framework for approximating UFPP by Bonsma et al. [FOGS 2011] and on a (4 + ε)-approximation algorithm for δ-small SAP instances (in which d_j ≤ δ · c_e, for every e ∈ I_j, for a sufficiently small constant δ ＞ 0). In our algorithm for δ-small instances, tasks are packed carefully in strips in a UFPP manner, and then a (1 + ε) factor is incurred by a reduction from SAP to UFPP in strips. The strips are stacked to form a SAP solution. Finally, we show-that SAP is strongly NP-hard, even with uniform weights and even if assuming the no bottleneck assumption.