2026-07-22T12:01:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11903 2024-03-06T10:48:58Z ddc:004 open_access

Fixed-Parameter Algorithms for Unsplittable Flow Cover Cristi, Andrés Mari, Mathieu Wiese, Andreas Unsplittable Flow Cover fixed parameter algorithms approximation algorithms 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 2000] and also a QPTAS [Höhn et al., ICALP 2014]. 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 slightly 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 f(k)⋅ n^O_ε(1) that outputs a solution with at most (1+ε)k tasks or assert 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrés Cristi and Mathieu Mari and Andreas Wiese 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.42 urn:nbn:de:0030-drops-119037 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.42 eng https://creativecommons.org/licenses/by/3.0/legalcode