Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat

摘要

Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a -approximation in trees which violates the budget by a factor of at most 2 (delta is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1- (1 - 1/delta) (delta)) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a -approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP).