第5回 最適化とアルゴリズム研究部会(12/7)開催のお知らせ

主査: 今堀 慎治(中央大学)

幹事: 胡  艶楠(名古屋大学)

●概要:

第5回の研究部会を2017年12月7日(木)に、名古屋大学にて開催いたしますので、以下の通りご案内させていただきます。

今回は名古屋大学の小野廣隆先生に講演していただきます。
小野先生は理論計算機科学,オペレーションズ・リサーチの周辺で,組合せ最適化をキーとした研究をしています.2017年4月1日付で,名古屋大学大学院情報学研究科・数理情報学専攻に,新しく小野廣隆研究室が立ち上がりました.
http://www.tcs.mi.i.nagoya-u.ac.jp

参加登録は不要ですので、当日会場までお越し下さい。多くの方のご参加をお待ちいたしております。

●日時:2017年12月7日(木) 16時30分~18時00分

●場所:

名古屋大学 情報学研究科棟 第一講義室(一階)
http://www.nagoya-u.ac.jp/access-map/

●講演者および概要

講演者: 小野廣隆(名古屋大学)

以下の2つのテーマについてご講演をいただきます.

タイトル1: 資金循環問題
要旨:
経済活動において,中央銀行には各銀行に資金を貸し付けることにより円滑な経済活動をサポートする役割がある.このため中央銀行は資金を準備しておく必要があるが,最低限どの程度の額を準備しておく必要があるか,あるいはどれだけ準備しておけば十分であるかはどの銀行がどの銀行に対してどれだけ負債を抱えているか,あるいは負債の返済をどのタイミングで行うかに強く依存する.本研究ではそれぞれを有向グラフにおける最適化問題Min-SFC,Max-SFCとしてモデル化し,その計算量を論じる.これらはいずれもNP困難であるが,特にMin-SFCは頂点数2の多重グラフ上,あるいは木幅2の単純グラフ上でも強NP困難であること,直径4の双方向木であってもNP困難であるが,双方向のスターでは多項式時間で解けることを示した.本研究は早川仁氏,石井利昌氏(北海道大学),宇野裕之氏(大阪府立大学)との共同研究である.

タイトル2: 有向グラフ上の被覆・支配問題
要旨:
無向グラフにおける頂点被覆問題と辺支配集合問題は,古典的なグラフ最適化問題であるが,有向グラフにおいては,向きと支配(被覆)の関連が必ずしも明瞭でないためか無向グラフと比べると対応する問題の研究は進んでいない.
本研究では,経済ネットワーク分析への応用を考えると「支配」の自然な解釈が存在することに着目し,有向グラフにおける距離-有向頂点被覆問題(r-VC)と距離-有向辺支配集合問題((p,q)-EDS)を定義した.例えば,経済ネットワークにおける特定の産業,取引が与える周りへの波及効果が有向グラフにおける「支配」に対応するため,波及効果を考慮した重要産業・取引の抽出はr-VC,(p,q)-EDSを解くことにより得られる.
まず,これらの問題が一般には計算困難(NP-困難,パラメータ化困難,近似困難)であることを示した.一方,木グラフにおいて,r-VCと(p,q)-EDSに対する多項式時間アルゴリズムが存在することを示した.さらに,p,q<=1のとき,(p,q)-EDSに対して,解サイズに関する-時間固定パラメータアルゴリズムが存在することを示した.
本研究は土中哲秀氏(九州大学),Naomi Nishimura氏(ウォータールー大学)との共同研究である.

●懇親会

研究会終了後、会場付近で懇親会を企画しております。
懇親会に参加を希望される方は、12月5日(火曜日)までに、以下のメールアドレスまでご連絡くださいますようお願い申し上げます。

胡(yannanhu@nagoya-u.jp