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.ICALP.2017.67
URN: urn:nbn:de:0030-drops-74154
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7415/
Go to the corresponding LIPIcs Volume Portal

Wiese, Andreas

A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time

pdf-format:
LIPIcs-ICALP-2017-67.pdf (0.5 MB)

Abstract

Unsplittable Flow on a Path (UFP) is a well-studied 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 fixed-parameter 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 fixed-parameter 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 Fixed-Parameter Running Time}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{67:1--67:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7415},
  URN =		{urn:nbn:de:0030-drops-74154},
  doi =		{10.4230/LIPIcs.ICALP.2017.67},
  annote =	{Keywords: Combinatorial optimization, Approximation algorithms, Fixed-parameter algorithms, Unsplittable Flow on a Path}
}

Keywords: Combinatorial optimization, Approximation algorithms, Fixed-parameter algorithms, Unsplittable Flow on a Path
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI