Timezone: »

Stochastic Network Design in Bidirected Trees
Xiaojian Wu · Daniel Sheldon · Shlomo Zilberstein

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D

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.

Author Information

Xiaojian Wu (Facebook)
Daniel Sheldon (University of Massachusetts Amherst)
Shlomo Zilberstein (Univ of Mass)

More from the Same Authors