Back to search

University of Waterloo

Approximation Algorithms for Graph Protection Problems

Abstract

dc:description.abstract

We study a budgeted cut problem known as Graph Protection, where the goal is to remove edges of a given graph in order to protect valuable nodes from stochastic, infectious threats. This problem was recently proposed by Shmoys and Spencer to model challenges associated with wildfire prevention when resources are limited and only probabilistic data of ignition location is known. The input consists of a graph with node values and edge costs, a budget, and probabilistic data signifying the likelihood a set of nodes will ignite; the goal is to remove a set of edges with total cost at most the budget so as to maximize the expected protected value unreachable from these stochastic ignition scenarios. Our focus is on the design of approximation algorithms for Graph Protection when an ignition scenario can contain an arbitrary number of nodes, a setting mostly left open in the literature. Our main positive result is the design of constant-factor approximation algorithms for Graph Protection when the input graph is a tree and each node has an independent chance of being an ignition point. We also show that in the general case when ignition probabilities are defined by a distribution over subsets of nodes, the problem becomes at least as hard as the Densest k-Subgraph problem and thus, such an approximation algorithm is unlikely to exist.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lange, Alexander

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9396

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lange, Alexander. Approximation Algorithms for Graph Protection Problems. University of Waterloo, 2015. http://hdl.handle.net/10012/9396