Rounded Dynamic Programming for Tree-Structured Stochastic Network Design

Xiaojian Wu, Daniel Sheldon, and Shlomo Zilberstein. Rounded Dynamic Programming for Tree-Structured Stochastic Network Design. Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI), 479-485, Quebec City, Canada, 2014.

Abstract

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.

Bibtex entry:

@inproceedings{WSZaaai14,
  author	= {Xiaojian Wu and Daniel Sheldon and Shlomo Zilberstein},
  title		= {Rounded Dynamic Programming for Tree-Structured Stochastic
                   Network Design},
  booktitle     = {Proceedings of the Twenty-Eighth Conference on Artificial
                   Intelligence},
  year		= {2014},
  pages		= {479-485},
  address       = {Quebec City, Canada},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WSZaaai14.html}
}

shlomo@cs.umass.edu