線形マトロイドパリティを用いたメトリック巡回セールスマン問題の近似アルゴリズム

加藤　拓

（指導教員：岩田　覚　教授／ 数理情報第7研究室）

研究概要

重み付き線形マトロイドパリティを用いてメトリック巡回セールスマン問題の近似解を得る新たなアルゴリズムに関して，Christofidesのアルゴリズムと同様に, 近似比保証の1.5がタイトであることを証明した．さらに，計算機実験を通じて，実際上高精度であることを示した.

近似比が1.5に収束する例

卒論の感想

アルゴリズムの精度を理論的観点と実用的観点の両方から研究したのは良い経験となった.この半年間の卒業研究を通して得た経験を今後の研究生活に活かしていきたいと思う.