スピングラス理論の最適化問題への展開による近似手法の典型評価法の確立

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

本課題はスピングラス理論を組合せ最適化問題のみならず、問題に対する近似アルゴリズムの典型（平均）近似精度の解析に展開することを目的としている。より具体的には、ランダムに与えられる組合せ最適化問題に対する貪欲法、確率伝搬法、線形計画緩和の典型近似性能を平均場近似を用いることで解析的に導出し、それらの典型性能比較を可能とする。これにより、情報科学、ネットワーク理論、統計力学に関わる最適化問題の典型的な困難さへの数理的理解を深化させることを目指した。本年度は本研究課題の最終年度であるため、研究成果全体の総括を行う。(1) 最小頂点被覆問題のランダム化として、従来よりも広いクラスのランダムグラフにおいて上記３アルゴリズムの典型性能比較を実施した。その結果、先行研究で多用されるランダムグラフでの典型性能の大小関係とは異なるランダムグラフが存在することを見出し、大小関係の分類を行った。本成果は国際論文誌に発表されている。また、最大カバー問題における上記３アルゴリズムの典型性能比較により、確率伝搬法の優位性を解析的に示し、同等の最悪近似性能をもつ貪欲法と線形計画緩和が異なる典型近似性能をもつことを明らかにした（現在論文準備中）。これらの成果は、典型近似性能が最悪近似性能と同等に重要であり、また系統的な解析を要することを示唆している。(2) 最適化問題と統計的推論問題の類似性に着目し、統計力学的手法による集団検査法におけるブーリアン圧縮センシングの効率的近似アルゴリズム提案とその典型性能解析を行った。これにより、従来法よりも効率的な手法提案という実用面と典型性能評価という理論面の両面での進展を実現した（現在論文準備中）。(3) 線形計画緩和を用いた数値計算により最適化問題の典型的な困難さとグラフ構造の相関を数値的に評価した（現在論文準備中）。