<p>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$.</p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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)?</p>

CC BY-SA 3.0
2014-11-09T16:36:32.133Z
Do you have a single target $t$ or multiple terminals $\{t_i\}$?
R B
CC BY-SA 3.0
2014-11-09T16:46:57.897Z
Multiple terminals.
user2150466
CC BY-SA 3.0
2014-11-09T16:52:03.057Z
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$?
R B
CC BY-SA 3.0
2014-11-09T17:01:24.617Z
Thanks for ur response. Can you please elaborate? what would be the approximation ratio?
user2150466
CC BY-SA 3.0
2014-11-09T17:02:00.567Z
Notice that this problem is NP hard. We cant solve it exactly.
user2150466
CC BY-SA 3.0
2014-11-09T17:02:29.710Z
This is why I asked that you define the problem formally. I'm not sure I understood your intent.
R B
CC BY-SA 3.0
2014-11-09T18:18:22.007Z
Ok :) I did some changes in the description. I noticed that I shouldn't call it unsplittable flow anymore, because there is a single path to each terminal. I'll change the title.
user2150466
CC BY-SA 3.0
2014-11-09T22:35:31.347Z
OK, now I get you. Note that it's different from the definition I'm familiar with (asused by [Kleinberg](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CFDDB07F8BDD8E3BB4995E088E5C0B1D?doi=10.1.1.44.1029&rep=rep1&type=pdf) and [Dinic](http://cgi.di.uoa.gr/~vassilis/co/co-papers/dinitz99.pdf) ) where the goal is to satisfy *all* demands, which seems to be trivial on trees.
R B
CC BY-SA 3.0
2014-11-09T23:12:29.480Z
I'v skimmed through his paper. The settings are different. My problem is a very natural generalization of the knapsack problem. I think someone should'v worked on it, or maybe there is a similar fptas to the knapsack.
user2150466
CC BY-SA 3.0
2014-11-09T23:27:04.487Z
Recent papers consider a similar setting, but not with a single source. [(Anagnostopoulos 2013)](https://www.google.ae/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCEQFjAA&url=http%3A%2F%2Fwww.idsia.ch%2F~grandoni%2FPubblicazioni%2FAGLW13ipco.pdf&ei=BPdfVKjxI4S4OsjhgdAH&usg=AFQjCNG0DNziFK6da9zaOjDX5eSBQctNKQ&sig2=FCM3idt-IxmxXA5pWRtYpw) obtained a constant integrity gap for the multi-source case on a path.
user2150466
CC BY-SA 3.0
2014-11-09T23:27:43.203Z
Before this work, [(Chekuri 2009)](https://www.google.ae/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCQQFjAB&url=http%3A%2F%2Fwww.cs.princeton.edu%2F~aene%2Fpapers%2Fufp-approx.pdf&ei=y_dfVKnmJMnVPaTNgagP&usg=AFQjCNGLIohje5EXMySM1rHC1tG6inK7Ow&sig2=OgdIA97d2pmiM9zYjpy6BA) obtained only a logarithmic gap for the tree topology. The fact is that single source simplifies the problem a lot (in my opinion).
user2150466
<combinatorics><flow-problems>
Single source multicommodity flow on a path or tree
user2150466
# Single source multicommodity flow on a path or tree

(Asked by: username_0 on 2014-11-09)

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)?

**Tags:** combinatorics, flow-problems

> **Comments:**
> **username_1**: Do you have a single target $t$ or multiple terminals $\{t_i\}$?  
> **username_0**: Multiple terminals.  
> **username_1**: 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$?  
> **username_0**: Thanks for ur response. Can you please elaborate? what would be the approximation ratio?  
> **username_0**: Notice that this problem is NP hard. We cant solve it exactly.  
> **username_1**: This is why I asked that you define the problem formally. I'm not sure I understood your intent.  
> **username_0**: Ok :) I did some changes in the description. I noticed that I shouldn't call it unsplittable flow anymore, because there is a single path to each terminal. I'll change the title.  
> **username_1**: OK, now I get you. Note that it's different from the definition I'm familiar with (asused by [Kleinberg](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CFDDB07F8BDD8E3BB4995E088E5C0B1D?doi=10.1.1.44.1029&rep=rep1&type=pdf) and [Dinic](http://cgi.di.uoa.gr/~vassilis/co/co-papers/dinitz99.pdf) ) where the goal is to satisfy *all* demands, which seems to be trivial on trees.  
> **username_0**: I'v skimmed through his paper. The settings are different. My problem is a very natural generalization of the knapsack problem. I think someone should'v worked on it, or maybe there is a similar fptas to the knapsack.  
> **username_0**: Recent papers consider a similar setting, but not with a single source. [(Anagnostopoulos 2013)](https://www.google.ae/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCEQFjAA&url=http%3A%2F%2Fwww.idsia.ch%2F~grandoni%2FPubblicazioni%2FAGLW13ipco.pdf&ei=BPdfVKjxI4S4OsjhgdAH&usg=AFQjCNG0DNziFK6da9zaOjDX5eSBQctNKQ&sig2=FCM3idt-IxmxXA5pWRtYpw) obtained a constant integrity gap for the multi-source case on a path.  
> **username_0**: Before this work, [(Chekuri 2009)](https://www.google.ae/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCQQFjAB&url=http%3A%2F%2Fwww.cs.princeton.edu%2F~aene%2Fpapers%2Fufp-approx.pdf&ei=y_dfVKnmJMnVPaTNgagP&usg=AFQjCNGLIohje5EXMySM1rHC1tG6inK7Ow&sig2=OgdIA97d2pmiM9zYjpy6BA) obtained only a logarithmic gap for the tree topology. The fact is that single source simplifies the problem a lot (in my opinion).  

---

## 0 answers

