On Approximating Storage Allocation Problems as Good as Their Siblings

Three particularly important and well-studied
questions in this domain are the Unsplittable Flow on a Path problem
(UFP), the Maximum Weight Independent Set of Rectangles problem (MWISR),
and the 2-dimensional geometric knapsack problem. In this paper, we
study the Storage Allocation Problem (SAP) which is a natural combination
of those three questions. Given is a path with edge capacities and
a set of tasks that are specified by start and end vertices, demands,
and profits. The goal is to select a subset of the tasks that
can be drawn as non-overlapping rectangles underneath
the capacity profile, the height of a rectangles corresponding to
the demand of the respective task. This problem arises naturally in
settings where a certain available bandwidth has to be allocated contiguously
to selected requests.

While for 2D-knapsack and UFP there are polynomial time (2+epsilon)-approximation
algorithms known [Jansen and Zhang, SODA 2004] [Anagnostopoulos
et al., SODA 2014] the best known approximation factor for SAP is
9+epsilon [Bar-Yehuda, SPAA 2013]. In this paper, we level
the understanding of SAP and the other two problems above by presenting
a polynomial time (2+epsilon)-approximation algorithm for SAP.
A typically difficult special case of UFP and its variations arises
if all input tasks are relatively large compared to the capacity of
the smallest edge they are using. For that case, we even obtain a
pseudopolynomial time exact algorithm for SAP.
Finally, we show that any solution to UFP can be transformed to a solution
to SAP by either losing only a constant factor of the profit or by increasing the
edge capacities by a constant factor.