Resource minimization for fire containment

Parinya Chalermsook*, Julia Chuzhoy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

18 Citations (Scopus)

Abstract

We consider the following model for fire containment. We are given an undirected graph G = (V, E) with a source vertex s where the fire starts. At each time step, the firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease and its containment via vaccination. We focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T ⊆ V of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to the vertices of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an O(log* n)-approximation LP-rounding algorithm for RMFC on trees. We also show that an even stronger LP relaxation has an integrality gap of Ω(log* n) on trees. Finally, we consider RMFC on directed layered graphs, and show an O(log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation.

Original languageEnglish
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Pages1334-1349
Number of pages16
Publication statusPublished - 2010
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Austin, United States
Duration: 17 Jan 201019 Jan 2010
Conference number: 21

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CityAustin
Period17/01/201019/01/2010

Fingerprint Dive into the research topics of 'Resource minimization for fire containment'. Together they form a unique fingerprint.

Cite this