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

1. Ageev, A.A., Sviridenko, M.: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307–328 (2004)

   Article  MathSciNet  MATH  Google Scholar 

2. Engelberg, R., Könemann, J., Leonardi, S., Naor, J(S.): Cut Problems in Graphs with a Budget Constraint. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 435–446. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

3. Finney, M.A.: A computational method for optimising fuel treatment locations. International Journal of Wildland Fire 16, 702–711 (2007)

   Article  Google Scholar 

4. Hayrapetyan, A., Kempe, D., Pál, M., Svitkina, Z.: Unbalanced Graph Cuts. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 191–202. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

5. Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: 40th STOC, pp. 255–264 (2008)

   Google Scholar 

6. Shmoys, D., Spencer, G.: Full paper: Approximation algorithms for fragmenting a graph against a stochastically-located threat, http://people.orie.cornell.edu/gms39/images/documents/gsfragment.pdf

7. Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters 32, 41–43 (2004)

   Article  MathSciNet  MATH  Google Scholar 

8. Wei, Y., Rideout, D., Kirsch, A.: An opt. model for locating fuel treatments across a landscape to reduce expected fire losses. Can. J. of Forest Res. 38, 868–877 (2008)

   Article  Google Scholar 

Download references