Resource Minimization for Fire Containment

(RMFC): Given a graph G=(V,E) with source vertex s where the fire starts and
a subset T of vertices that need to be protected from the fire. At each time
step, firefighters can save up to k vertices, while the fire spreads from
burning vertices to all their neighbors that have not been saved so far. The
goal is to minimize k -- the number of firefighters -- while ensuring that
no vertices in T burn. This model has been used to abstract the spread
mechanism of fire and perfectly contagious diseases. In this talk, we show
an O(log* n)-approximation LP-rounding algorithm for RMFC on trees, with a
matching lower bound on the integrality gap of the LP.

Joint work with Julia Chuzhoy (SODA'10)