氏名: 小野 孝男 (d953401)

論文題目: 充足最大化問題の近似アルゴリズムに関する研究


論文概要

充足最大化問題(MAX SAT)とは,積和形式(CNF)のブール論理式とその各節 に対する正の実数の重みが与えられたときに,充足する節の重みの和を最大に するような変数への真理値の割当てを求める問題である.この問題は知識デー タベースにおける推論や組合せ回路のテストパターン生成にも応用できるなど, 実用的にも重要な問題である.しかし,MAX SATはNP-困難であることが知られ ており,P=NPでなければ多項式時間で最適解を求めることはできない.したがっ て近似アルゴリズムを開発することが重要であるが,最近になって多項式時間 近似アルゴリズムの範囲では近似性能に理論的な上限があることがわかった. したがって,近似性能の限界を求めることが理論的に興味深い.近似アルゴリ ズムとしては確率的手法に基づくJohnsonのアルゴリズムが知られていたが, 最近,線形計画問題や半定値計画問題に緩和するGoemansとWilliamsonによる 近似アルゴリズムが提案され,活発な研究がなされている.

本論文では以下の2つの結果について発表する.まず,入力の各節に含まれる リテラルの数をたかだか3個に制限した3-充足最大化問題(MAX 3SAT)を考え る.従来の方法では0.765という近似率しか得られないが,本論文では半定値 計画問題に緩和するGoemansとWilliamsonのアルゴリズムを改良して,それを 他の近似アルゴリズムと組合せたアルゴリズムを提案する.確率的手法による 解析を行い,このアルゴリズムが0.769-近似アルゴリズムとなることを示す. 次に,MAX SATを考える.この問題に対しては0.758-近似アルゴリズムが知ら れているが,本論文では近似アルゴリズムで得られる近似解に摂動を加えるこ との効果を調べる.摂動とは与えられた解の各変数の値をそれぞれ独立に一定 の確率で変化させて新しい解を生成するという手法である.これまでに知られ ている3つのアルゴリズムの解に適切な摂動を加え,組合せることで0.768-近 似アルゴリズムが得られることを示す.最後に,ここに挙げた近似アルゴリズ ムはすべて確率的アルゴリズムであるため,これを同じ性能が保証される決定 性アルゴリズムに変換するための方法についても述べる.


目次に戻る