# New integrality gap results for the firefighters problem on trees

Parinya Chalermsook, Daniel Vaz*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

4 Sitaatiot (Scopus)

## Abstrakti

In the firefighter problem on trees, we are given a tree G = (V,E) together with a vertex s ∈ V where the fire starts spreading. At each time step, the firefighters can pick one vertex while the fire spreads from burning vertices to all their neighbors that have not been picked. The process stops when the fire can no longer spread. The objective is to find a strategy that maximizes the total number of vertices that do not burn. This is a simple mathematical model, introduced in 1995, that abstracts the spreading nature of, for instance, fire, viruses, and ideas. The firefighter problem is NP-hard and admits a (1−1/e) approximation via LP rounding. Recently, a PTAS was announced in [1].(The (1 − 1/e) approximation remained the best until very recently when Adjiashvili et al. [1] showed a PTAS. Their PTAS does not bound the LP gap.) The goal of this paper is to develop better understanding on the power of LP relaxations for the firefighter problem. We first show a matching lower bound of (1 − 1/e + ϵ) on the integrality gap of the canonical LP. This result relies on a powerful combinatorial gadget that can be used to derive integrality gap results in other related settings. Next, we consider the canonical LP augmented with simple additional constraints (as suggested by Hartke). We provide several evidences that these constraints improve the integrality gap of the canonical LP: (i) Extreme points of the new LP are integral for some known tractable instances and (ii) A natural family of instances that are bad for the canonical LP admits an improved approximation algorithm via the new LP. We conclude by presenting a 5/6 integrality gap instance for the new LP.

Alkuperäiskieli Englanti Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers Springer 65-77 13 10138 LNCS 9783319517407 https://doi.org/10.1007/978-3-319-51741-4_6 Julkaistu - 2017 A4 Artikkeli konferenssijulkaisussa Workshop on Approximation and Online Algorithms - Aarhus, TanskaKesto: 25 elok. 2016 → 26 elok. 2016Konferenssinumero: 14

### Julkaisusarja

Nimi Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10138 LNCS 03029743 16113349

### Workshop

Workshop Workshop on Approximation and Online Algorithms WAOA Tanska Aarhus 25/08/2016 → 26/08/2016

## Sormenjälki

Sukella tutkimusaiheisiin 'New integrality gap results for the firefighters problem on trees'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.