本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

グラフアルゴリズムの平均感度解析
講演者:吉田悠一(国立情報学研究所)
2020年12月17日(木)13時30分〜15時00分 Zoom
応用分野の多くの問題はグラフ上の最適化問題として定式化することができ、それらを解くアルゴリズムは、意思決定や知識発見の道具として幅広く利用されている。しかし観測精度の限界などにより、入力として与えられたグラフが真実を反映しているとは限らない。そのような状況下でもアルゴリズムの出力の品質を保つためには、アルゴリズムに真のグラフを入力した場合と、その(大きな)部分グラフを入力した場合とで、出力する解があまり離れないことが望ましい。本講演では、この問題に対処するために講演者らが最近定式化した「平均感度」について紹介した後、具体的な問題に対する平均感度の小さいアルゴリズムや他の計算モデルとの関連について説明する。