[Colloquium] Talk by Parinya Chalermsook, U of C on February 23, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, February 23, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Parinya Chalermsook

From:		University of Chicago

Web page:	http://www.cs.uchicago.edu/people/parinya

Title: Resource Minimization for Fire Containment

Abstract: We consider the Resource Minimization Fire Containment problem (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)  



Please note that refreshments will be served prior to the talk at 2:30 in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100209/fdaca8f6/attachment.htm