Rounded Dynamic Programming for Tree-Structured Stochastic Network Design

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 nearoptimal solutions much faster than an existing technique.

Authors

• Xiaojian Wu
• Daniel Sheldon University of Massachusetts, Amherst
• Shlomo Zilberstein University of Massachusetts Amherst

Keywords

No keywords are indexed for this paper.