New Integrality Gap Results for the Firefighters Problem on Trees

Parinya Chalermsook, Daniel Vaz

The firefighter problem is NP-hard and admits a $(1-1/e)$ approximation based on rounding the canonical LP. In this paper, we first show a matching integrality gap of $(1-1/e+\epsilon )$ o…