We study the Unsplittable Flow problem $$\mathsf {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.#R##N##R##N#Our main result is an $$Ok\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\log ^2 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.#R##N##R##N#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.#R##N##R##N#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 $$\mathsf {APX}$$-hard if the input data is arbitrary.
['Anna Adamaszek', 'Parinya Chalermsook', 'Alina Ene', 'Andreas Wiese']
Submodular Unsplittable Flow on Trees