木における消防士問題に対する近似アルゴリズムの改良

概要

論文の詳細を見る
消防士問題は火災の延焼,伝染病,そしてコンピューターウィルスの拡散等をモデル化した問題である.本論文では根付き木上の消防士問題を扱う.消防士間題は最大次数が3の根付き木上に限定してもNP困難であることが知られている.本論文では,既存の近似アルゴリズムの近似率を改善する手法を2つ提案する.まず最初に,陰的列挙を用いた手法を提案する.この手法を既存の(1-1/e)-近似アルゴリズムに適用すると,(1-(k-1)/((k-1)e+1))-近似アルゴリズムが得られる.ただし,kは根の子供の数を表している.例えば3分木の場合は,k=3であるので近似率は(1-(k-1)/((k-1)e+1))≧0.6892となり,既存の近似率1-1/e≈0.6321より良い値となっている.2つめの手法は,3分木に限定した改善手法であり,帰納的な考え方を用いている.この手法を既存の(1-1/e)-近似に用いると,0.6976-近似アルゴリズムが得られる.これら2つの手法を併用すると,3分木における消防士問題に対する0.7144-近似アルゴリズムを構築することができる.
2010-06-18