Skip to main content
2 of 2
added 45 characters in body
lchen
  • 327
  • 4
  • 14

Steiner tree subject to non-trivial constraint

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.

lchen
  • 327
  • 4
  • 14