Approximation algorithms for fragmenting a graph against a stochastically-located threat

DOI10.1007/s00224-014-9548-6zbMath1311.90086OpenAlexW2059230032MaRDI QIDQ2344215

David B. Shmoys, Gwen Spencer

Publication date: 12 May 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9548-6

zbMATH Keywords

optimizationgraphsapproximation algorithmssustainabilitystochasticmultistagecontaining contagion

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation algorithms (68W25)

Cites Work

• A note on maximizing a submodular set function subject to a knapsack constraint
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Approximability of the firefighter problem. Computing cuts over time
• Cut Problems in Graphs with a Budget Constraint
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Algorithms – ESA 2005
• Unnamed Item
• Unnamed Item
• Unnamed Item