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

详细信息    查看全文

• 作者：David B. Shmoys ; Gwen Spencer
• 关键词：Approximation algorithms ; Multistage ; Stochastic ; Optimization ; Graphs ; Containing contagion ; Sustainability
• 刊名：Theory of Computing Systems
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：56
• 期：1
• 页码：96-134
• 全文大小：900 KB
• 参考文献：1. Ageev, A., Sviridenko, M.: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307-28 (2004). CrossRef
  2. Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the firefighter problem. Algorithmica. 62(1-2), 520-36 (2012). CrossRef
  3. Chalermsook, P., Chuzhoy, J.: Resource minimization for fire containment. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA -0, pages 1334-349, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.
  4. Engelberg, R., K?nemann, J., Leonardi, S., Naor, J.: Cut problems in graphs with a budget constraint. 7th Lat., 435-46 (2006).
  5. Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Australas. J. Combin. 43, 57-7 (2009).
  6. Finney, M.: A computational method for optimising fuel treatment locations. Int. J. Wildland Fire. 16, 702-11 (2007). CrossRef
  7. Goemans, M. X., Williamson, D. P.: A new 3/4-approximation algorithm for max sat. SIAM J. Discret. Math. 7, 313-21 (1994). CrossRef
  8. Hartnell, B.: Firefighter! an application of domination. Presentation, 25th Manitoba Conference of Combinatorial Mathematics and Computing, 1995.
  9. Hayrapetyan, A., Kempe, D., Pál, M., Svitkina, Z.: Unbalanced graph cuts. 13th Eur. Symp. Algoritm. (ESA), 191-02 (2005).
  10. R?cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. 40th Symp. Theory Comput. (STOC), 255-64 (2008).
  11. Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32, 41-3 (2004). CrossRef
  12. Wei, Y., Rideout, D., Kirsch, A.: An optimization model for locating fuel treatments across a landscape to reduce expected fire losses. Can. J. For. Resour. 38, 868-77 (2008). CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490

文摘

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 \((1-\frac {1}{e}) -approximation in trees which violates the budget by a factor of at most 2 (δ 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/δ) δ) 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 \((1-\frac {1}{e})\) -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).