TY - JOUR
AU - Wu, Xiaojian
AU - Sheldon, Daniel
AU - Zilberstein, Shlomo
PY - 2014/06/20
Y2 - 2024/05/17
TI - Rounded Dynamic Programming for Tree-Structured Stochastic Network Design
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 28
IS - 1
SE - Computational Sustainability and Artificial Intelligence
DO - 10.1609/aaai.v28i1.8761
UR - https://ojs.aaai.org/index.php/AAAI/article/view/8761
SP -
AB - <p> We develop a fast approximation algorithm called rounded dynamic programming (RDP) for stochastic network design problems on directed trees. The underlying model describes phenomena that spread away from the root of a tree, for example, the spread of influence in a hierarchical organization or fish in a river network. Actions can be taken to intervene in the network—for some cost—to increase the probability of propagation along an edge. Our algorithm selects a set of actions to maximize the overall spread in the network under a limited budget. We prove that the algorithm is a fully polynomial-time approximation scheme (FPTAS), that is, it finds (1−ε)-optimal solutions in time polynomial in the input size and 1/ε. We apply the algorithm to the problem of allocating funds efficiently to remove barriers in a river network so fish can reach greater portions of their native range. Our experiments show that the algorithm is able to produce near-optimal solutions much faster than an existing technique. </p>
ER -