License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.44
URN: urn:nbn:de:0030-drops-119053
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11905/
Cristi, Andrés ;
Wiese, Andreas
Better Approximations for General Caching and UFP-Cover Under Resource Augmentation
Abstract
In the Unsplittable Flow on a Path Cover (UFP-cover) problem we are given a path with a demand for each edge and a set of tasks where each task is defined by a subpath, a size and a cost. The goal is to select a subset of the tasks of minimum cost that together cover the demand of each edge. This problem models various resource allocation settings and also the general caching problem. The best known polynomial time approximation ratio for it is 4 [Bar-Noy et al., STOC 2000]. In this paper, we study the resource augmentation setting in which we need to cover only a slightly smaller demand on each edge than the compared optimal solution. If the cost of each task equals its size (which represents the natural bit-model in the related general caching problem) we provide a polynomial time algorithm that computes a solution of optimal cost. We extend this result to general caching and to the packing version of Unsplittable Flow on a Path in their respective natural resource augmentation settings. For the case that the cost of each task equals its "area", i.e., the product of its size and its path length, we present a polynomial time (1+ε)-approximation for UFP-cover. If additionally the edge capacities are in a constant range we compute even a solution of optimal cost and also obtain a PTAS without resource augmentation.
BibTeX - Entry
@InProceedings{cristi_et_al:LIPIcs:2020:11905,
author = {Andr{\'e}s Cristi and Andreas Wiese},
title = {{Better Approximations for General Caching and UFP-Cover Under Resource Augmentation}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11905},
URN = {urn:nbn:de:0030-drops-119053},
doi = {10.4230/LIPIcs.STACS.2020.44},
annote = {Keywords: General caching, unsplittable flow cover, approximation algorithm, resource augmentation}
}
|
Keywords: |
|
General caching, unsplittable flow cover, approximation algorithm, resource augmentation |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
