BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv5.3.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for 
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20230322T153000
DTEND;TZID=UTC:20230322T163000
DTSTAMP:20260507T194411
CREATED:20230319T132045Z
LAST-MODIFIED:20230319T132045Z
UID:7186-1679499000-1679502600@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Mohammad Salavatipour\, U. Alberta
DESCRIPTION:Approximation Schemes for Resource Minimization for Fire Containment\nResource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of\nharmful spreading phenomena on a graph. In the RMFC problem on trees\, we are given an undirected\ntree G\, and a vertex r where the fire starts at\, called root. At each time step\, the firefighters\ncan protect up to B vertices of the graph while the fire spreads from burning vertices to all their\nneighbors that have not been protected so far. The task is to find the smallest B that allows for\nsaving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2\neven on trees unless P = NP. \nIn this talk we present an asymptotic QPTAS for RMFC on trees. More specifically\, let \eps > 0\,\nand F be an instance of RMFC where the optimum number of firefighters to save all the leaves is\nOPT(F). We present an algorithm which uses at most \ceil(1 + \eps )OPT(F)\rceil many firefighters at each\ntime step and runs in time n^O(\log\log n). This suggests that the existence of an asymptotic PTAS is\nplausible especially since the exponent is O(log log n). \n————————————————————-\nJoin Zoom Meeting\nhttps://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09 \nMeeting ID: 864 1523 0827\nPasscode: 835547
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-mohammad-salavatipour-u-alberta/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette%20Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
END:VCALENDAR