权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

将自旋玻璃理论应用于优化问题，建立近似方法的典型评估方法

基本信息

批准号：
15J09001
负责人：
高邉賢史
金额：
$ 1.09万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2015
资助国家：
日本
起止时间：
2015-04-24 至 2017-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15J09001/
关键词：
統計力学キャビティ法線形計画法レプリカ対称性相転移

项目摘要

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

This paper aims at solving the problem of approximate precision and typical (average) approximate precision of optimization problem by combining theory and optimization theory. Specific optimization problems, such as optimization problems, linear optimization problems, and linear optimization problems. The typical difficulties of optimization problems in information science, science theory and statistical mechanics are discussed in this paper. This year is the final year of this research project, and the research results are summarized. (1)The minimum vertex coverage problem is solved by comparing the typical performance of the three vertex coverage problems. The results of the previous study showed that the size relationship between the typical performance and the difference between the typical performance and the size relationship was different. This work is published in international papers. 3. Comparison of typical performance of linear plans, comparison of optimality of analytical methods, comparison of equivalent and most approximate performance, comparison of linear plans, comparison of typical approximate performance of linear plans, comparison of linear The results of this study are as important as the typical approximation performance and the analysis of the system. (2)The similarity of optimization problems and statistical inference problems is discussed. The method of statistical mechanics is used to analyze the typical performance of optimization problems. This paper is currently under preparation. (3)The typical difficulties of linear plan mitigation and numerical value calculation in optimization problems are evaluated in relation to numerical values of linear structure (now in preparation).