Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ quantity of good from $s$ to $t_i$ along a path $P_i$. The problem is to find the set of path $P_i$ for each destination $t_i$ subject to edge capacity constraint. Is this problem NP_hard? Moreover, if each edge is associated with a cost $w_i$ and the problem is to find the set of paths $\{P_i\}$ of minimum total cost. How to develop algorithm solving this variant?
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
This problem is called single-source unsplittable flow problem [1]. This problem is NP-hard. The special case where there are only two nodes includes the bin packing problem.
- [1]: J. M. Kleinberg, "Single-source unsplittable flow," Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 68-77.
