Stochastic Network Design in Bidirected Trees
We investigate the problem of stochastic network design in bidirected trees. In this problem, an underlying phenomenon (e.g., a behavior, rumor, or disease) starts at multiple sources in a tree and spreads in both directions along its edges. Actions can be taken to increase the probability of propagation on edges, and the goal is to maximize the total amount of spread away from all sources. Our main result is a rounded dynamic programming approach that leads to a fully polynomial-time approximation scheme (FPTAS), that is, an algorithm that can find (1− )-optimal solutions for any problem instance in time polynomial in the input size and 1/ . Our algorithm outperforms competing approaches on a motivating problem from computational sustainability to remove barriers in river networks to restore the health of aquatic ecosystems.
The paper generalize a previous work on stochastic network design on a directed rooted tree to model influence propagating from a single source to the whole network. In this paper, the directions on the edges are in both way and not directed away from the source as in the previous work. The paper generalizes the rounded dynamic programming approach from the previous work to get an FPTAS for the more general setting. The idea is to discretize the space of possible outcomes at any subtree. For each subtree rooted at a vertex v, there are 3 parameters defining the outcome: the influence within the subtree, the influence going through v to the subtree, and the influence going from the subtree through v to the rest of the tree. This crucially depends on the assumption that the reward factor/influence for 2 nodes s and t must be of the form h(s)*h(t) for a fixed function h. This assumption allows for aggregating influence going through v into 2 parameters as described above. The writing is clear and easy to follow. The dynamic programming approach is standard in the literature for designing FPTAS and in this particular case, quite similar to previous work. The setup is more general than in previous work but there is still the restriction that the reward factor for 2 nodes s and t must be of the form h(s)*h(t) for a fixed function h. It is only mentioned that this restriction is a good match for the application without any further explanation.== added after rebuttal ==Thanks for adding applications where the reward factors of the form h(s)*h(t) make sense.