Abstrakt. Vi tillhandahåller approximationsalgoritmer för flera varianter av brandmansproblem på allmänna grafer. Brandmännens problem modellerar fallet där en infektion eller annan diffus process (såsom en idé, ett datorvirus, eller en brand) sprider sig genom ett nätverk, och vårt mål är att stoppa denna infektion genom att använda riktade vaccinationer. Specifikt, Vi är tillåtet att vaccinera på de flesta B noder per tid-steg (för vissa budget B), med målet att minimera effekten av infektionen. Svårigheten med detta problem kommer från dess temporal komponent, eftersom vi måste välja noder att vaccinera vid varje gång-steg medan infektionen sprider sig genom nätverket, vilket leder till begrepp om "snitt över tiden". Vi överväger två versioner av problemet med brandmän: en "icke-spridande" modell, där vaccinering av en nod endast innebär att denna nod inte kan smittas; och en "spridande" modell där själva vaccinationen är en smittsam process, som i fallet där infektionen är en skadlig idé, och vaccinet till det är en annan smittsam idé. Vi ger komplexa och approximativa resultat för problem på båda modellerna.
REF inledde studien av spridningsmodellen, där vaccinationen också sprids via nätverket.
Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity
{'venue': 'ISAAC', 'journal': None, 'mag_field_of_study': ['Computer Science']}