Given a edge-weighted transportation network modeled as a graph. A source node $s$ needs to send an object to a set of $k$ destination nodes $t_i$, $1\le i\le k$. For the transportation, $s$ needs to construct a tree rooted at itself. The particularity in my problem is that each branch node of the tree should make copies of the object (e.g., by using 3D printing) so as to send to multiple destinations, but the copying operation is not perfect. Specifically, if a branch node makes $c$ copies, the quality of each copy $q'=q\frac{2c+1}{3c}$, where $q$ denotes the quality of the object before copying and $q'$ denotes the quality of each copy after copying, given that the original quality of the object is initialized to $1$. Here the $c$ copies include the original one, whose quality also degrades to $q'$. My problem is to seek a min-weight steiner tree subject to that the copy recieved by each $t_i$ has quality $\ge \theta_i$, a threshold.
11
- $\begingroup$ This is not a well-defined question. If you want an answer, you need to be more specific. Now, for example, an optimal solution would be for $s$ to make $k$ copies itself and send one to each $t_i$. $\endgroup$domotorp– domotorp2022-06-02 07:08:44 +00:00Commented Jun 2, 2022 at 7:08
- $\begingroup$ @domotorp Thank you for pointing out this. I have modified the problem. $\endgroup$lchen– lchen2022-06-03 04:17:34 +00:00Commented Jun 3, 2022 at 4:17
- $\begingroup$ How would behave the quality along a path from $s$ through all $t_i$'s? Is $c=1$ all along, or should $c$ be taken as $2$ on the $t_i$'s because the destination nodes are supposed to absorb one copy? $\endgroup$Claude Chaunier– Claude Chaunier2022-06-06 17:27:59 +00:00Commented Jun 6, 2022 at 17:27
- $\begingroup$ @ClaudeChaunier If a relay node is also a destination node, it should take $c=2$ as it needs a copy for itself. $\endgroup$lchen– lchen2022-06-07 02:19:23 +00:00Commented Jun 7, 2022 at 2:19
- $\begingroup$ I'm still somewhat confused: do you assume that the transportation cost over an edge is the product of the edge weight and the number of objects transported over that edge (this would, indeed, make it sometimes advantageous to make copies at the branching points instead of transporting everything from the source) or you just restrict transportation over each edge to one object only (that will force copying). $\endgroup$fedja– fedja2022-06-07 23:50:51 +00:00Commented Jun 7, 2022 at 23:50
| Show 6 more comments