Timezone: »
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
-
2022 Spotlight: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2022 Poster: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2021 Poster: Relaxed Marginal Consistency for Differentially Private Query Answering »
Ryan McKenna · Siddhant Pradhan · Daniel Sheldon · Gerome Miklau -
2020 Poster: Advances in Black-Box VI: Normalizing Flows, Importance Weighting, and Optimization »
Abhinav Agrawal · Daniel Sheldon · Justin Domke -
2020 Poster: Permute-and-Flip: A new mechanism for differentially private selection »
Ryan McKenna · Daniel Sheldon -
2020 Spotlight: Permute-and-Flip: A new mechanism for differentially private selection »
Ryan McKenna · Daniel Sheldon -
2019 Poster: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Spotlight: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Poster: Differentially Private Bayesian Linear Regression »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Differentially Private Bayesian Inference for Exponential Families »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Importance Weighting and Variational Inference »
Justin Domke · Daniel Sheldon -
2018 Poster: Inferring Latent Velocities from Weather Radar Data using Gaussian Processes »
Rico Angell · Daniel Sheldon -
2016 Poster: Probabilistic Inference with Generating Functions for Poisson Latent Variable Models »
Kevin Winner · Daniel Sheldon -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2011 Poster: Collective Graphical Models »
Daniel Sheldon · Thomas Dietterich -
2010 Poster: MAP Estimation for Graphical Models by Likelihood Maximization »
Akshat Kumar · Shlomo Zilberstein -
2009 Poster: Complexity of Decentralized Control: Special Cases »
Martin Allen · Shlomo Zilberstein -
2009 Poster: Robust Value Function Approximation Using Bilinear Programming »
Marek Petrik · Shlomo Zilberstein -
2009 Spotlight: Robust Value Function Approximation Using Bilinear Programming »
Marek Petrik · Shlomo Zilberstein -
2007 Spotlight: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen -
2007 Poster: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen