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

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

• 批准号: 08J02878
• 负责人: 安藤 映
• 金额: $ 0.77万
• 依托单位: Fukuoka University of Education
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08J02878/
• 关键词: グラフ最適化問題; 確率変数の枝重み; 正規分布; 指数分布; 有向非巡回グラフ; 最長路問題

本年度は,様々なグラフ最適化問題について確率変数の枝重みが与えられる場合に,最適解重みの分布を近似的に計算するための高速なアルゴリズムを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年における本研究申請時点の目的を達成し,さらに今後の研究のための挑戦的な課題に対する解決法の検討を行うことができた.

在今年，当在2009年10月的国际会议上，在国际会议上介绍了一种随机变量为各种图形优化问题的分支权重时，用于近似最佳解决方案权重的分布的高速算法。通过此介绍，在2007年进行了这项研究时，就提出了各种图形优化问题。此外，上一年的结果在2009年4月的AAAC2009，国际会议和2009年TAMC2009的TAMC2009（同行评审）上发布了2009年5月的国际会议。截至2009年1月。截至2009年1月，这些论文在2009年11月24日在2009年12月24日在2009年12月23日发表。参观了西蒙·弗雷泽大学（加拿大）和约瑟夫。彼得斯教授，Binay Bhattacharya教授，Tiko名誉教授Kameda教授就概率优化问题解决方案进行了联合研究。 SAGA 2009上介绍的算法是一个函数，该函数迅速计算出一个函数，该函数为图形优化问题的最佳解决方案权重的分布函数提供了下限。该算法的计算时间作为解决确定性优化问题的时间和计算解决方案候选数的时间的总和，并且可以保证逻辑近似比。这里的近似值是最佳解决方案（实际上很难计算）与算法输出功能输出之间的反向函数比率的上限。此外，当分支权重以随机变量为独立于组合优化问题时，可以使用该算法，例如最小跨越树问题，最大匹配问题和旅行推销员问题。接下来，除了研究计划的范围之外，该演讲是在TAMC 2009上进行的。我们试图扩大结果。关于有向无环图的结构，我们引入了某些参数，当该图被常数抑制时，我们使用一种方法来近似图中最长路径长度的分布函数。今年，我们试图对应于任意的图形，但是很难用这些图的任意小计算误差有效地计算分布函数。此外，在西蒙·弗雷泽大学（Simon Fraser University）的联合研究中，我们讨论了计算计算机网络中广播时间分布时间的类似问题，其中一个通道中的消息传输时间以随机变量的形式提供。如上所述，在今年，实现了2007年这项研究时的目标，我们能够进一步探索解决挑战性问题的解决方案。

项目成果

On the Distribution of the Longest Path Length in a Directed Acyclic Graph with Exponentially Distributed Edge Weights

边权指数分布的有向无环图中最长路径长度的分布

• 发表时间: 2008
• 作者: Ei Ando;et al.
• 通讯作者: et al.

Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

计算 DAG 中随机最长路径长度的精确分布函数

• 发表时间: 2009
• 作者: E.Ando;et al.
• 通讯作者: et al.

A Counting-Based Approximation of the Distribution Function of the Longest Path Length in Directed Acyclic Graphs

有向无环图中最长路径长度分布函数的基于计数的近似

• 发表时间: 2008
• 作者: Ei Ando;et al.
• 通讯作者: et al.

連続分布枝重み付DAGに対する最長路長さ分布の計算

连续分布边加权DAG的最长路径长度分布计算

• 发表时间: 2009
• 作者: 安藤映;小野廣隆;定兼邦彦;山下雅史
• 通讯作者: 山下雅史

Computing the Exact Distribution Function of the Longest Path Length in IDAGs with Exponentially Distributed Edge Lengths

计算具有指数分布边长的 IDAG 中最长路径长度的精确分布函数

• 发表时间: 2009
• 作者: 安藤映;小野廣隆;定兼邦彦;山下雅史
• 通讯作者: 山下雅史