New Integrality Gap Results for the Firefighters Problem on Trees

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10138
• 期：1
• 页码：65-77
• 丛书名：Approximation and Online Algorithms
• ISBN：978-3-319-51741-4
• 卷排序：10138

文摘

In the firefighter problem on trees, we are given a tree \(G=(V,E)\) together with a vertex \(s \in 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.)