A Constant Factor Approximation Algorithm for the Storage Allocation Problem

作者：Bar Yehuda Reuven; Beder Michael; Rawitz Dror^*

来源：Algorithmica, 2017, 77(4): 1105-1127.

DOI：10.1007/s00453-016-0137-8

• Approximation algorithms
• Bandwidth allocation
• Rectangle packing
• Storage allocation
• Unsplittable flow

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 and a set J of tasks. Each edge has a capacity and each task is associated with a path in P, a demand and a weight . The goal is to find a maximum weight subset of tasks and a height function such that (i) , for every ; and (ii) if such that and , then . SAP can be seen as a rectangle packing problem in which rectangles can be moved vertically, but not horizontally. We present a polynomial time -approximation algorithm for SAP. Our algorithm is based on a variation of the framework for approximating UFPP by Bonsma et al. [FOCS 2011] and on a -approximation algorithm for -small SAP instances (in which , for every , for a sufficiently small constant ). In our algorithm for -small instances, tasks are packed carefully in strips in a UFPP manner, and then a factor is incurred by a reduction from SAP to UFPP in strips. The strips are stacked to form a SAP solution. Finally, we provide a -approximation algorithm for SAP on ring networks.

• 出版日期2017-4