■第12回研究会(2004年11月27日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『二項モデル上でのヨーロピアン・アジアンオプションの価格付けに対する精度保証付き近似解法』東北大学 塩浦昭義 氏
本講演では、二項モデル上でのヨーロピアン・アジアンオプションの 価格付けという問題について考える。この問題は計算困難な問題であり、 近似アルゴリズムの研究がさかんに行われてきた。 近年、 Aingworth, Motwani, および Oldham (2000) によって、 近似精度の保証された最初のアルゴリズムが提案された。 それ以降、いくつかの研究グループにより近似精度の改善がなされてきた。 本講演では、講演者のグループによる研究結果を中心として、これらの 精度保証付き近似アルゴリズムの紹介を行う。
 
16:10--18:00『格子構造を持つグラフのマルチカラーリング』上智大学 宮本裕一郎 氏
単純無向グラフに対して、隣接点間で同じ色を使わないように、 それぞれの点に複数色を割り当てることをマルチカラーリングという。 マルチカラーリングはスケジューリングなどの様々な場面で 現れることが知られている。 与えられたグラフが規則正しいものでも、 それぞれの点に割り当てなければならない色数がばらばらならば、 マルチカラーリングは難しいことが知られている。 本講演では、格子状に点が配置されたときにその点間の距離で 隣接関係が決まるグラフのマルチカラーリングを考え、 効率的にマルチカラリングできるための条件を整理する。 また、この結果により精度保証付き近似解法を構築可能である。
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.