Submodular unsplittable flow on trees

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en Adamaszek, Anna Chalermsook, Parinya Ene, Alina Wiese, Andreas 2018-03-16T10:31:19Z 2018-03-16T10:31:19Z 2018-11
dc.identifier.citation Adamaszek , A , Chalermsook , P , Ene , A & Wiese , A 2018 , ' Submodular unsplittable flow on trees ' Mathematical Programming , pp. 1-25 . DOI: 10.1007/s10107-017-1218-4 en
dc.identifier.issn 0025-5610
dc.identifier.issn 1436-4646
dc.identifier.other PURE UUID: 195a3a7d-29ed-4e04-bf8c-c8baa13a3af6
dc.identifier.other PURE ITEMURL:
dc.identifier.other PURE LINK:
dc.identifier.other PURE FILEURL:
dc.description.abstract We study the Unsplittable Flow problem ((Formula presented.)) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our main result is an (Formula presented.)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth (Formula presented.), we obtain an (Formula presented.) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation ratio for UFP on trees with a linear objective function. Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of Bonsma et al. (2014, FOCS), Anagnostopoulos et al. (Amazing 2+(Formula presented.) approximation for unsplittable flow on a path, SIAM, pp 26–41, 2014) for UFP on paths with a linear objective. Our relaxation is very structured, so it can be combined with the contention resolution framework of Chekuri et al. (2009, STOC). Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem. Additionally, we study the special case of UFP on trees with a linear objective and upward instances where, for each task, the source node is a descendant of the sink node. Such instances generalize UFP on paths. We build on the work of Bansal et al. (A quasi-PTAS for unsplittable flow on line graphs, ACM, pp 721–729, 2006) for UFP on paths and obtain a QPTAS for upward instances when the input data is quasi-polynomially bounded. We complement this result by showing that, unlike the path setting, upward instances are (Formula presented.)-hard if the input data is arbitrary. en
dc.format.extent 25
dc.format.extent 1-25
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartofseries Mathematical Programming en
dc.rights openAccess en
dc.subject.other Software en
dc.subject.other Mathematics(all) en
dc.subject.other 113 Computer and information sciences en
dc.title Submodular unsplittable flow on trees en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department University of Copenhagen
dc.contributor.department Professorship Chalermsook P.
dc.contributor.department University of Warwick
dc.contributor.department Max Planck Institute for Informatics
dc.contributor.department Department of Computer Science en
dc.subject.keyword Approximation algorithms
dc.subject.keyword Submodular functions
dc.subject.keyword Unsplittable flow problem
dc.subject.keyword Software
dc.subject.keyword Mathematics(all)
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201803161718
dc.identifier.doi 10.1007/s10107-017-1218-4
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account