Search

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.

text, 紀要論文 / Departmental Bulletin Paper

フレーズベース統計的機械翻訳では,連続する単語列(フレーズ)を翻訳の最小単位とした確率的規則に基づいて翻訳候補の順位付けを行い,最も確率の高い候補を出力とする.しかし,入力文のフレーズ区切りや翻訳前後の訳語関係(フレーズ対応)の組合せ数は膨大である.そのため,従来の統計的機械翻訳システムは,翻訳候補およびフレーズ区切り・対応に対して大胆な近似を行うことで探索空間を狭めており,厳密な確率の最大化をしていない.本稿では,フレーズ対応・区切りに関する厳密な確率最大化を行う問題を,フレーズベース翻訳において広く用いられているすべての素性を考慮可能な形式で整数線形計画問題として定式化し,それを翻訳候補のリランキングに応用する手法を提案・実装する.評価実験の結果,提案手法は有意に翻訳精度を改善することが示されると同時に,フレーズベース翻訳における探索の課題は,フレーズ対応ではなく翻訳候補文についてより多くの候補を評価することにあるという示唆が得られた.