Mömke, Tobias ;
Wiese, Andreas
Breaking the Barrier of 2 for the Storage Allocation Problem
Abstract
Packing problems are an important class of optimization problems. The probably most wellknown problem if this type is knapsack and many generalizations of it have been studied in the literature like Twodimensional Geometric Knapsack (2DKP) and Unsplittable Flow on a Path (UFP). For the latter two problems, recently the first polynomial time approximation algorithms with better approximation ratios than 2 were presented [Gálvez et al., FOCS 2017][Grandoni et al., STOC 2018]. In this paper we break the barrier of 2 for the Storage Allocation Problem (SAP), a problem which combines properties of 2DKP and UFP. In SAP, we are given a path with capacitated edges and a set of tasks where each task has a start vertex, an end vertex, a size, and a profit. We seek to select the most profitable set of tasks that we can draw as nonoverlapping rectangles underneath the capacity profile of the edges where the height of each rectangle equals the size of the corresponding task.
The problem SAP appears naturally in settings of allocating resources like memory, bandwidth, etc. where each request needs a contiguous portion of the resource. The best known polynomial time approximation algorithm for SAP has an approximation ratio of 2+ε [Mömke and Wiese, ICALP 2015] and no better quasipolynomial time algorithm is known. We present a polynomial time (63/32+ε) < 1.969approximation algorithm for the important case of uniform edge capacities and a quasipolynomial time (1.997+ε)approximation algorithm for nonuniform quasipolynomially bounded edge capacities. Key to our results are building blocks consisting of stairblocks, jammed tasks, and boxes that we use to construct profitable solutions and which allow us to compute solutions of these types efficiently. Finally, using our techniques we show that under slight resource augmentation we can obtain even approximation ratios of 3/2+ε in polynomial time and 1+ε in quasipolynomial time, both for arbitrary edge capacities.
BibTeX  Entry
@InProceedings{mmke_et_al:LIPIcs:2020:12493,
author = {Tobias M{\"o}mke and Andreas Wiese},
title = {{Breaking the Barrier of 2 for the Storage Allocation Problem}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {86:186:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12493},
URN = {urn:nbn:de:0030drops124931},
doi = {10.4230/LIPIcs.ICALP.2020.86},
annote = {Keywords: Approximation Algorithms, Resource Allocation, Dynamic Programming}
}
29.06.2020
Keywords: 

Approximation Algorithms, Resource Allocation, Dynamic Programming 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 