Wiese, Andreas
A (1+epsilon)Approximation for Unsplittable Flow on a Path in FixedParameter Running Time
Abstract
Unsplittable Flow on a Path (UFP) is a wellstudied problem. It arises in many different settings such as bandwidth allocation, scheduling, and caching. We are given a path with capacities on the edges and a set of tasks, each of them is described by a start and an end vertex and a demand. The goal is to select as many tasks as possible such that the demand of the selected tasks using each edge does not exceed the capacity of this edge. The problem admits a QPTAS and the best known polynomial time result is a (2+epsilon)approximation. As we prove in this paper, the problem is intractable for fixedparameter algorithms since it is W[1]hard. A PTAS seems difficult to construct.
However, we show that if we combine the paradigms of approximation algorithms and fixedparameter tractability we can break the mentioned boundaries. We show that on instances with OPT=k we can compute a (1+epsilon)approximation in time 2^O(k log k)n^O_epsilon(1) log(u_max) (where u_max is the maximum edge capacity).
To obtain this algorithm we develop new insights for UFP and enrich a recent dynamic programming framework for the problem. Our results yield a PTAS for (unweighted) UFP instances where OPT is at most O(log n/log log n) and they imply that the problem does not admit an EPTAS, unless W[1]=FPT.
BibTeX  Entry
@InProceedings{wiese:LIPIcs:2017:7415,
author = {Andreas Wiese},
title = {{A (1+epsilon)Approximation for Unsplittable Flow on a Path in FixedParameter Running Time}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {67:167:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7415},
URN = {urn:nbn:de:0030drops74154},
doi = {10.4230/LIPIcs.ICALP.2017.67},
annote = {Keywords: Combinatorial optimization, Approximation algorithms, Fixedparameter algorithms, Unsplittable Flow on a Path}
}
07.07.2017
Keywords: 

Combinatorial optimization, Approximation algorithms, Fixedparameter algorithms, Unsplittable Flow on a Path 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 