最適化問題の近似アルゴリズムとその並列化

点击翻译按钮获取中文摘要

本研究では、2種類の最適化問題を考えた。最初の問題は最大部分グラフ問題(MSPと略す)である。多くの実用的な問題がMSPとして定式化できるが、ほとんどのMSPがNP困難である。そのため、MSPに対する近似アルゴリズムの研究が盛んに行なわれてきた。LiptonとTarjanは、人力を平面グラフに制御した場合のMSPを考え、その場合のMSPを解く一様の近似アルゴリズムを与えた。のちに、Bakerは実用性の面からLiptonとTarjanの近似アルゴリズムを改善し、人力を平面グラフに制限した場合のMSPを解く実用的な一様の近似アルゴリズムを与えた。本研究では、「Bakerの結果の中で要求される入力グラフの平面性は本質的であるのか?」という質問を考え、それに肯定的な答えがあることを証明した。もっと具体的に言えば、入力グラフの平面性という制限をK_<3,3>-freeかまたはK_5-freeに緩めてもMSPを解く実用的な一様の近似アルゴリズムがあることを示した。この結果を得るのに近年盛んに研究ささているtreewidthという概念を用いた。2番目に考えた問題は最短超文字列問題(shortest superstring problem)である。この問題はデータ圧縮とDNAの研究に応用性があるため、今まで盛んに研究されてきた。特に、この問題に対する近似アルゴリズムの研究は最近非常に盛んである。本研究以前に、この問題を解くNC近似アルゴリズムがいくつか既にあった。その中で最もよいのは本研究者によって得られた。本研究では、そのNC近似アルゴリズムの効率を更に改善した。