TY - GEN
T1 - A (2+ɛ)-approximation algorithm for the storage allocation problem
AU - Mömke, Tobias
AU - Wiese, Andreas
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - Packing problems are a fundamental class of problems studied in combinatorial optimization. Three particularly important and wellstudied 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 + ɛ)-approximation algorithms known [Jansen and Zhang, SODA 2004] [Anagnostopoulos et al., SODA 2014] the best known approximation factor for SAP is 9+ɛ [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+ɛ)-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.
AB - Packing problems are a fundamental class of problems studied in combinatorial optimization. Three particularly important and wellstudied 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 + ɛ)-approximation algorithms known [Jansen and Zhang, SODA 2004] [Anagnostopoulos et al., SODA 2014] the best known approximation factor for SAP is 9+ɛ [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+ɛ)-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.
UR - https://www.scopus.com/pages/publications/84950150704
U2 - 10.1007/978-3-662-47672-7_79
DO - 10.1007/978-3-662-47672-7_79
M3 - Conference contribution
AN - SCOPUS:84950150704
SN - 9783662476710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 973
EP - 984
BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
A2 - Halldorsson, Magnus M.
A2 - Kobayashi, Naoki
A2 - Speckmann, Bettina
A2 - Iwama, Kazuo
PB - Springer Verlag
T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Y2 - 6 July 2015 through 10 July 2015
ER -