Submodular unsplittable flow on trees
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Submodular unsplittable flow on trees. / Adamaszek, Anna Maria; Chalermsook, Parinya; Ene, Alina; Wiese, Andreas.
Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings. ed. / Quentin Louveaux; Martin Skutella. Springer, 2016. p. 337-349 (Lecture notes in computer science, Vol. 9682).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Submodular unsplittable flow on trees
AU - Adamaszek, Anna Maria
AU - Chalermsook, Parinya
AU - Ene, Alina
AU - Wiese, Andreas
N1 - Conference code: 18
PY - 2016
Y1 - 2016
N2 - We study the Unsplittable Flow problem (UFP) 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 O(k log n)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(log n), we obtain an O(log2 n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem and it matches the best approximation known 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., FOCS 2011; Anagnostopoulos et al., SODA 2014] for UFP on paths with a linear objective. Our relaxation is very structured and we can combine it with the contention resolution framework of [Chekuri et al., STOC 2011]. 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., STOC 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 APX-hard if the input data is arbitrary.
AB - We study the Unsplittable Flow problem (UFP) 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 O(k log n)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(log n), we obtain an O(log2 n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem and it matches the best approximation known 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., FOCS 2011; Anagnostopoulos et al., SODA 2014] for UFP on paths with a linear objective. Our relaxation is very structured and we can combine it with the contention resolution framework of [Chekuri et al., STOC 2011]. 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., STOC 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 APX-hard if the input data is arbitrary.
UR - http://www.scopus.com/inward/record.url?scp=84976642207&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-33461-5_28
DO - 10.1007/978-3-319-33461-5_28
M3 - Article in proceedings
AN - SCOPUS:84976642207
SN - 978-3-319-33460-8
T3 - Lecture notes in computer science
SP - 337
EP - 349
BT - Integer Programming and Combinatorial Optimization
A2 - Louveaux, Quentin
A2 - Skutella, Martin
PB - Springer
Y2 - 1 June 2016 through 3 June 2016
ER -
ID: 176375581