計算問題の並列化可能性と並列化不能性

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

本研究では、最適化問題の並列近似可能性に焦点を当てた。大まかに言うと、二つの問題を考えた。最初の問題は最短超文字列問題(shortest superstring problem)である。この問題はデータ圧縮とDNAの研究に応用性があるため、今まで盛んに研究されてきた。特に、この問題に対する近似アルゴリズムの研究は最近非常に盛んである。本研究の前に、Rytterらはこの問題のNC近似アルゴリズム(圧縮率=1/(4+ε))とRNC近似アルゴリズム(近似率=2+5/6、圧縮率=1/2)を提案した。本研究では、Rytterらの結果を改善できた。具体的には、この問題のNCアルゴリズム(圧縮率=1/(3+ε))とRNC近似アルゴリズム(近似率=2+50/63、圧縮率=38/63)を設計できた。次に考えた問題はグラフを(できるだけ少ない)森に分割する問題である。この問題はVLSIに応用があるが、NP困難である。そこで、本研究ではこの問題の並列近似アルゴリズムを設計しようとした。まず、平面グラフを三つの森に分割する最適のNCアルゴリズムを設計し、このアルゴリズムを利用して平面グラフ上で定義される様々なNP困難な最適化問題の並列近似アルゴリズム(近似率=3)を設計した。次に平面グラフの拡張となる疎なグラフに着目した。この拡張は問題を難しくした。疎なグラフを森に分割する一般的なNCアルゴリズムを設計できなかったが、どのような条件の下でNCアルゴリズムがあるかを明らかにした。この条件を利用して、平面グラフの特別な拡張であるK_<3,3>-freeグラフやK_5-freeグラフを森に分割するNCアルゴリズムを設計できた。