Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
added 45 characters in body
Source Link
lchen
  • 327
  • 4
  • 14

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 maximizes the sum of qualities of the copiescopy recieved by each $t_i$ has quality $\ge \theta_i$, a threshold.

Given a 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 steiner tree that maximizes the sum of qualities of the copies recieved by $t_i$.

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.

Notice added Authoritative reference needed by lchen
Bounty Started worth 50 reputation by lchen
Source Link
lchen
  • 327
  • 4
  • 14

Steiner tree subject to non-trivial constraint

Given a 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 steiner tree that maximizes the sum of qualities of the copies recieved by $t_i$.