Submodular unsplittable flow on trees
研究了树上带子模目标函数的不可分割流问题，提出一个O(k log n)近似算法，其中k是树的路径宽度，对任意树达到O(log² n)近似比，是首个非平凡近似保证。
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(log 2 n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation