News

Seminar

Approximation Algorithms for the Firefighter Problem

Ameya Hate

Date: February 24, 2010
Lally 02 - 11:00 a.m. to 12:00 p.m.

Abstract:

We provi de approximation algorithms for several variants of the Firefighter problem on general graphs. The Firefighter problem models the case where a diffusive process such as an infection (or an idea, a computer virus, a fire) is spreading through a network, and our goal is to contain this infection by using targeted vaccinations. Specifically, we are allowed to vaccinate at most a fixed number (called the budget) of nodes per time-step, with the goal of minimizing the effect of the infection. The difficulty of this problem comes from its temporal component, since we must choose nodes to vaccinate at every time-step while the infection is spreading through the network, leading to notions of cuts over time. We consider two versions of the Firefighter problem: a non-spreading model, where vaccinating a node means only that this node cannot be infected; and a spreading model where the vaccination itself is an infectious process, such as in the case where the infection is a harmful idea, and the vaccine to it is another infectious beneficial idea. We look at two measures: the MaxSave measure in which we want to maximize the number of nodes which are not infected given a fixed budget, and the MinBudget measure, in which we are given a set of nodes which we have to save and the goal is to minimize the budget. We study the approximability of these problems in both models.

Last updated: February 23, 2010