Given a graph $G=(V,E)$, a set of terminals $T = \{t_1,\ldots, t_n\}$, and a single source $s$, where $s\in V$ and $T \subseteq V\backslash \{s\}$. Each terminal $i$ is associated with a demand $d_i$ and a utility $u_i$. Moreover, each edge $e \in E$ has a capacity $c_e$.

The objective is to maximize $$\sum_{i=1}^n x_i u_i$$ subject to edge capacities: for all $e=(u,v) \in E$, $$\sum_{i \text{ is rooted by } v }^n d_i x_i \le c_e$$ where $x_i \in \{0,1\}$ is a decision variable.

We assume $G$ is a tree (or path for simplicity). This implies that for each demand $i$ there is only a single path. The problem is to decide which demand to select in order to attain the maximum utility, while respecting edge capacities.

Unsplittable flow is an old problem and has several variations and settings. I'v seen recent research papers considering unsplittable flow on a path (but with multiple sources), as well as older papers considering single source but on general toplogy.

In fact this problem is still NP-hard as it generalizes knapsack. Is there any paper considering this setting: utility maximization, single source (multiple terminals), and tree/path topology)?

  • $\begingroup$ Do you have a single target $t$ or multiple terminals $\{t_i\}$? $\endgroup$
    – R B
    Nov 9 '14 at 16:36
  • $\begingroup$ Multiple terminals. $\endgroup$ Nov 9 '14 at 16:46
  • $\begingroup$ Can you please explain what you mean by unsplittable flow on trees? Why can't you simply check, for all vertices $v$ of the tree, if the capacity of the path leading from $s$ to $v$ is at least the sum of demands of all terminals in the subtree who's root is $v$? $\endgroup$
    – R B
    Nov 9 '14 at 16:52
  • $\begingroup$ Thanks for ur response. Can you please elaborate? what would be the approximation ratio? $\endgroup$ Nov 9 '14 at 17:01
  • 1
    $\begingroup$ Notice that this problem is NP hard. We cant solve it exactly. $\endgroup$ Nov 9 '14 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.