Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14497
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBonsma, Paul
dc.contributor.authorSchulz, Jens
dc.contributor.authorWiese, Andreas
dc.date.accessioned2021-12-17T10:09:50Z-
dc.date.available2021-12-17T10:09:50Z-
dc.date.issued2011
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15724-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14497-
dc.description.abstractWe study the unsplittable flow problem on a path P. We are given a set of n tasks. Each task is specified by a sub path of P, a demand, and a profit. Moreover, each edge of P has a given capacity. The aim is to find a subset of the tasks with maximum profit, for which the given demands can be simultaneously routed along P, subject to the capacities. The best known polynomial time approximation algorithm for this problem achieves a performance ratio of O (log n) and the best known hardness result is weak NP-hardness. In this paper, we firstly show that the problem is strongly NP-hard, even when the capacities are constant, and all demands are chosen from {1,2,3}. Secondly, we present the first polynomial time constant-factor approximation algorithm for this problem, achieving an approximation factor of 7+epsilon for any epsilon>0. This answers an open question from Bansal et al. (SODA'09). We employ a novel framework which reduces the problem to instances where the capacities of the edges differ by at most a constant factor. Moreover, for the difficult "large" tasks - for which in particular the straightforward linear program has an integrality gap of Omega(n) - we present a new geometrically inspired dynamic program.en
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherUnsplittable Flowen
dc.subject.otherapproximation algorithmen
dc.subject.otherschedulingen
dc.subject.otherrectangle intersectionen
dc.titleA Constant Factor Approximation Algorithm for Unsplittable Flow on Pathsen
dc.typeResearch Paperen
tub.accessrights.dnbfreeen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2011, 06en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
dc.type.versionsubmittedVersionen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-006-2011.pdf
Format: Adobe PDF | Size: 543.44 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.