- This event has passed.
Atlantic Graph Theory Seminar: Mohammad Salavatipour, U. Alberta
March 22, 2023 @ 3:30 pm - 4:30 pm
Approximation Schemes for Resource Minimization for Fire Containment
Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of
harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected
tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters
can protect up to B vertices of the graph while the fire spreads from burning vertices to all their
neighbors that have not been protected so far. The task is to find the smallest B that allows for
saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2
even on trees unless P = NP.
In this talk we present an asymptotic QPTAS for RMFC on trees. More specifically, let \eps > 0,
and F be an instance of RMFC where the optimum number of firefighters to save all the leaves is
OPT(F). We present an algorithm which uses at most \ceil(1 + \eps )OPT(F)\rceil many firefighters at each
time step and runs in time n^O(\log\log n). This suggests that the existence of an asymptotic PTAS is
plausible especially since the exponent is O(log log n).
Join Zoom Meeting
Meeting ID: 864 1523 0827