日時：2005年 7月28日（木） 15:00〜18:00 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 山内 直哉（京都大学大学院情報学研究科通信情報システム専攻 修士課程１年） 「安定結婚問題に対する局所探索近似アルゴリズムの改良」講演要旨 ・ 古賀 祐一（京都大学大学院情報学研究科数理工学専攻 修士課程２年） 「MAX-2-SATに対する分枝限定法」講演要旨 ・ 花谷 陽一（京都大学大学院情報学研究科通信情報システム専攻 博士課程１年） 「3彩色不能な平面グラフの構成法」講演要旨
安定結婚問題に対する局所探索近似アルゴリズムの改良
山内 直哉（京都大学大学院情報学研究科通信情報システム専攻 修士課程１年）
安定結婚問題において，同順位リストと不完全リストの存在を許した問題に対して最 大サイズの安定マッチングを見つける問題を考える． この問題はNP困難であり，現在知られている中で最も良い近似アルゴリズムは， （$2-c\frac{\log N}{N}$）-近似アルゴリズムである （ここで，$c$は任意の正定数であり，$N$は入力中の男性の数である）． 今回の我々の研究では，この近似度を$2-c\frac{1}{\sqrt{N}}$に改良することに成 功した（$c$は$c \leq \frac{1}{4 \sqrt{6}}$を満たす正定数である）．
MAX-2-SATに対する分枝限定法
古賀 祐一（京都大学大学院情報学研究科数理工学専攻 修士課程２年）
MAX-2-SATとは，n変数よりなるm個の節で各節のリテラル数が高々2で あるものが与えられたとき，充足節の重みの和を最大にする変数の割当を求める問題であり，NP困難であることが知られている．本研究では, MAX-2-SATを分枝限定法によって厳密に解くアルゴリズムを提案する．分枝限定法においては, 生成する部分問題の数と計算時間を下げるために, 以下の二つが特に重要である. 一つは論理的なルールにより厳密性を失うことなく変数固定，論理式の簡略化，限定操作等を行うもので, これは変換規則と呼ばれる. もう一つは, 下界値テストにおける, 精度の高い下界値計算のアルゴリズムである. 本発表では，変換規則と下界値計算のそれぞれに対して従来にはなかった新しい手法を提案し, それに基づいた計算実験の結果について報告する.
3彩色不能な平面グラフの構成法
花谷 陽一（京都大学大学院情報学研究科通信情報システム専攻 博士課程１年）
3彩色不能なグラフを網羅的に構成可能なグラフ算法として、Haj\ 'os calculus が知られている。任意の3彩色不能なグラフが多項式回の規則の適用で構成できるならばNP = co-NP となるが、現在のところ多項式回では構成できないようなグラフの族は知られていない。この問題に対するアプローチとして、制限されたグラフの族におけるグ ラフ算法を考える。我々は、平面グラフ上のグラフ算法に着目し、グラフ算法を示し、健全かつ完全であることを証明した。