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

確率的なシステム上の最適化問題に対する高速近似アルゴリズム

随机系统优化问题的快速逼近算法

基本信息

批准号：
08J02878
负责人：
安藤映
金额：
$ 0.77万
依托单位：
Fukuoka University of Education
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2008
资助国家：
日本
起止时间：
2008 至 2009
项目状态：
已结题

项目摘要

本年度は,様々なグラフ最適化問題について確率変数の枝重みが与えられる場合に,最適解重みの分布を近似的に計算するための高速なアルゴリズムを2009年10月に国際会議のSAGA2009(査読つき)において発表した.この発表内容をもって,平成19年における本研究の申請時点での研究計画を達成した.また,前年度の研究成果を2009年4月に国際会議のAAAC2009,2009年5月に国際会議のTAMC2009(査読つき)においてそれぞれ発表した.2009年1月時点でJournal of Discrete Algorithmsに採録決定された論文が2009年12月に出版された.2009年11月24日から2010年2月23日にかけてサイモンフレーザー大学(カナダ)を訪問し,Joseph Peters教授・Binay Bhattacharya教授・Tiko Kameda名誉教授と確率的な最適化問題の解法についての共同研究を行った.SAGA2009において発表したアルゴリズムは,グラフ最適化問題の最適解重みの分布関数について下界を与える関数を高速に計算するものである.このアルゴリズムの計算時間は確定的な最適化問題を解く時間と,解候補の数を計算する時間の和として与えられ,論理的な近似比の保証がある.ここでいう近似比とは,(実際には計算の難しい)最適解の分布関数とアルゴリズムの出力した関数との間の逆関数の比の上界である.また,このアルゴリズムは最小全域木問題・最大マッチング問題・巡回セールスマン問題などの組み合わせ最適化問題について,その枝重みが互いに独立な確率変数として与えられる場合に用いる事ができる.次に,研究計画の範囲を超えて,TAMC2009において発表した結果を拡張する事を試みた.有向非巡回グラフの構造について,あるパラメータκ々を導入し,このκが定数で抑えられる場合にそのグラフ中での最長路長さの分布関数を近似計算する手法を対象とした.今年度はこのたが任意に大きいグラフに対応することを試みたが,そのようなグラフについて任意に小さな計算誤差で分布関数を効率的に計算する事は,今回のアプローチでは難しい.また,サイモンフレーザー大学における共同研究では類似の問題として,一通信路におけるメッセージ伝達時間が確率変数として与えられる計算機ネットワークでのブロードキャスト時間の分布を計算する問題について考察した.以上のように,本年度においては平成19年における本研究申請時点の目的を達成し,さらに今後の研究のための挑戦的な課題に対する解決法の検討を行うことができた.

This year, the optimization problem of the optimal solution was solved by calculating the approximate distribution of the optimal solution weight in the case of the accuracy ratio and the weight ratio. The results were presented at the SAGA2009 International Conference in October 2009. The content of this report was reviewed and the research plan was completed in 1999. AAAC2009 International Conference, April 2009 May 2009 TAMC2009 International Conference (Review) January 2009 Journal of Discrete Algorithms December 2009 Publication November 24, 2009 February 23, 2010 University (Review) Interview with Professor Joseph Peters, Professor Binay Bhattacharya and Professor Tiko Kameda Emeritus on joint research on the solution of optimization problems with accuracy. SAGA 2009 presents a table on the distribution of optimal solutions to optimization problems. The calculation time of the optimization problem is determined by the solution time of the optimization problem, the calculation time of the candidate number of the solution, and the approximate ratio of the logic. The upper bound of the ratio of the distribution relations of the optimal solution to the output relations of the optimal solution to the inverse relations of the optimal solution. The minimum global problem, the maximum global problem, the circular problem, the group optimization problem, the branch weight problem, the independent accuracy rate problem, and the case use problem. Secondly, the scope of the research project has been expanded, and the results announced at TAMC2009 will be announced. In the case of directional non-circular path structure, the maximum path length in the path is approximately calculated. This year, the number of errors in the calculation of the distribution of errors in the calculation of the efficiency of the system is arbitrarily large, and the number of errors in the calculation of the efficiency is arbitrarily small. A joint study of computer science and technology in universities has investigated similar problems in computing the distribution of time in a communication network. This year, the goal of this study was achieved in the 19th year of this year, and the solution to the challenge of future research was discussed.