Improved Approximation Algorithms for Firefighter Problem on Trees
Improved Approximation Algorithms for Firefighter Problem on Trees
复制标题
DOI：
10.1587/transinf.e94.d.196
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Yutaka Iwaikawa;Naoyuki Kamiyama;Tomomi Matsui
中科院分区：
文献类型：
--
作者：
Yutaka Iwaikawa;Naoyuki Kamiyama;Tomomi Matsui
消防员问题用于模拟火灾、传染病和计算机病毒的传播。本文讨论的是有根树上的消防员问题。众所周知，即使对于最大度为 3 的有根树，消防员问题也是 NP 困难的。我们提出了改进给定近似算法的技术。首先，我们引入隐式枚举技术。通过将该技术应用于现有的 (1-1/e) 近似算法，当根有 k 个子节点时，我们获得 $(1- {k-1 \\over (k-1)e + 1})$ 近似算法。对于三叉树，k=3，因此近似比满足 $(1- {k-1 \\over (k-1)e + 1})$ ≥ 0.6892，这改进了现有结果 1-1/e ≥ 0.6321。第二种技术基于后向归纳法，改进了三元树上消防员问题的近似算法。如果我们将该技术应用于现有的 (1-1/e) 近似算法，我们将获得 0.6976 近似算法。最后，我们结合上述两种技术，得到了三叉树上消防员问题的 0.7144 近似算法。
The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing (1-1/e)-approximation algorithm, we obtain $(1- {k-1 \\over (k-1)e + 1})$-approximation algorithm when a root has k children. In case of ternary trees, k=3 and thus the approximation ratio satisfies $(1- {k-1 \\over (k-1)e + 1})$ ≥ 0.6892, which improves the existing result 1-1/e ≥ 0.6321. Second technique is based on backward induction and improves an approximation algorithm for firefighter problem on ternary trees. If we apply the technique to existing (1-1/e)-approximation algorithm, we obtain 0.6976-approximation algorithm. Lastly, we combine the above two techniques and obtain 0.7144-approximation algorithm for firefighter problem on ternary trees.