Maximizing the Spread of Cascades Using Network Design
Daniel Sheldon, Bistra Dilkina, Adam Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla Gomes, David Shmoys, William Allen, Ole Amundsen, William Vaughan
We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dy- namics by adding nodes or edges to the net- work. Our motivating application is one in spatial conservation planning, where a cas- cade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formu- lation that combines elements from network design and stochastic optimization. Our ap- proach results in solutions with stochastic op- timality guarantees and points to conserva- tion strategies that are fundamentally dier- ent from naive approaches.
PDF Link: /papers/10/p517-sheldon.pdf
AUTHOR = "Daniel Sheldon
and Bistra Dilkina and Adam Elmachtoub and Ryan Finseth and Ashish Sabharwal and Jon Conrad and Carla Gomes and David Shmoys and William Allen and Ole Amundsen and William Vaughan",
TITLE = "Maximizing the Spread of Cascades Using Network Design",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "517--526"