TY - JOUR

T1 - Fixed-Parameter Algorithms for Unsplittable Flow Cover

AU - Cristi, Andrés

AU - Mari, Mathieu

AU - Wiese, Andreas

N1 - Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/2

Y1 - 2023/2

N2 - The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of (Formula presented.) that outputs a solution with at most (1 + Ɛ)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + ε in the cost of the selected tasks.

AB - The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of (Formula presented.) that outputs a solution with at most (1 + Ɛ)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + ε in the cost of the selected tasks.

KW - Approximation algorithms

KW - Fixed parameter algorithms

KW - Unsplittable flow cover

UR - http://www.scopus.com/inward/record.url?scp=85116038968&partnerID=8YFLogxK

U2 - 10.1007/s00224-021-10048-7

DO - 10.1007/s00224-021-10048-7

M3 - Article

AN - SCOPUS:85116038968

SN - 1432-4350

VL - 67

SP - 89

EP - 124

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -