Faster (1 + ϵ)-approximation for unsplittable flow on a path via resource augmentation and back

Fabrizio Grandoni, Tobias Mömke, Andreas Wiese

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Unsplittable flow on a path (UFP) is an important and well-studied problem. We are given a path with capacities on its edges, and a set of tasks where for each task we are given a demand, a subpath, and a weight. The goal is to select the set of tasks of maximum total weight whose total demands do not exceed the capacity on any edge. UFP admits an (1+ε)-approximation with a running time of n^{O_{ε}(poly(log n))}, i.e., a QPTAS {[}Bansal et al., STOC 2006; Batra et al., SODA 2015{]} and it is considered an important open problem to construct a PTAS. To this end, in a series of papers polynomial time approximation algorithms have been developed, which culminated in a (5/3+ε)-approximation {[}Grandoni et al., STOC 2018{]} and very recently an approximation ratio of (1+1/(e+1)+ε) < 1.269 {[}Grandoni et al., 2020{]}. In this paper, we address the search for a PTAS from a different angle: we present a faster (1+ε)-approximation with a running time of only n^{O_{ε}(log log n)}. We first give such a result in the relaxed setting of resource augmentation and then transform it to an algorithm without resource augmentation. For this, we present a framework which transforms algorithms for (a slight generalization of) UFP under resource augmentation in a black-box manner into algorithms for UFP without resource augmentation, with only negligible loss.
Original languageEnglish
Title of host publication29th Annual European Symposium on Algorithms (ESA 2021)
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-15
Number of pages15
ISBN (Electronic)9783959772044
DOIs
Publication statusPublished - 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume204
ISSN (Print)1868-8969

Bibliographical note

Conference held: September 6-8, 2021, Lisbon, Portugal (Virtual Conference).

Funding

FundersFunder number
California Postsecondary Education Commission
Horizon 2020 Framework Programme695614
European Research Council389792660
Deutsche Forschungsgemeinschaft439522729
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung200020B_182865/1
Fondo Nacional de Desarrollo Científico y Tecnológico1200173, 1170223

    Fingerprint

    Dive into the research topics of 'Faster (1 + ϵ)-approximation for unsplittable flow on a path via resource augmentation and back'. Together they form a unique fingerprint.

    Cite this