第 12 回研究会
- 日時: 2020 年 8 月 31 日 (月) 13:30--17:00 (開場は 13:00 頃)
- 会場: ウェブ会議システム Zoom
- 講演 1
- 講演者: 馬原凌河氏 (京都大学 大学院理学研究科 数学・数理解析専攻)
- 講演題目: 頂点近傍重み付きシュタイナー木問題に対する近似アルゴリズムの設計
- 講演概要: 最小コストシュタイナー木問題は最も古典的な NP 困難問題のひとつである.
無向グラフと非負の辺コスト関数, そしてターミナルと呼ばれる頂点部分集合が与えられたとき, すべてのターミナルを連結にするような総コスト最小の部分グラフを見つける問題である.
目的関数を変えることで, この問題の様々な変種を考えることができる.
頂点周りの辺コストの最大値の各頂点における和を最小にする最小パワーシュタイナー木問題や, 頂点に重みが付加した頂点重み付きシュタイナー木問題などが例として挙げられる.
本講演では, これらを一般化した問題に対する近似アルゴリズムの設計を紹介する.
- 講演 2
- 講演者: 汪玉柱氏 (筑波大学 大学院システム情報工学研究科 社会工学専攻)
- 講演題目: 半正定値行列錐の疎緩和に関する最近の話題
- 講演概要: 理論的に半正定値計画問題 (SDP) は多項式時間で任意の精度に解け, 優れたソルバーも多数提供されているが, 問題のサイズによっては現実的な時間内で解くことが困難な場合がある.
このような困難に対処する一つの方法は, 制約を与える半正定値行列錐をより計算しやすい集合に緩和することである.
緩和集合としては, 線形計画問題 (LP) で判定できる優対角行列集合 (DD), 2 次錐計画問題で判定できるスケーリング優対角行列集合 (SDD), 小行列式の半正定値性を用いた疎 SDP 緩和などが提案されているが, 本発表ではこれらに関する最近の研究成果を紹介する.
特に発表者らが提案した, DD を含み SDD に含まれる LP 適用可能な緩和集合や, Blekherman et al. (2020) が示した疎 SDP 緩和錐と半正定値錐の距離に関する理論的な性質を緩和集合に拡張した結果などについて述べる予定である.
- 講演 3
- 講演者: 清水伸高氏 (東京大学 大学院情報理工学系研究科 数理情報学専攻)
- 講演題目: エキスパンダーグラフ上の合意モデル
- 講演概要: 合意モデルでは, 各頂点が 2 種類どちらかの意見を持つグラフを考え, 各頂点が共通のプロトコルに従い隣接頂点と通信しながら自身の意見を同時に更新していく過程を解析する.
特に, 全頂点が同一の意見を持つまでにかかるステップ数 (合意時間) が重要である.
本研究では, 既存の様々な合意モデルを特殊ケースとして含む一般的なモデルを提案し, そのモデルがエキスパンダーグラフ上で高速に合意に至ることを示す.
既存研究は特定のモデルに対して意見の初期状態に様々な仮定をおいた上での合意時間の上界を得ていた.
一方で本研究の結果はそのような仮定をおかずに既存結果と同程度の合意時間の上界を得たため, 既存結果の単純な拡張のみならずより強い主張も得ている.
本研究は中央大学の白髪丈晴氏との共同研究である.
- 参加費用: 無料
- 参加資格: 自由 (会員/非会員不問)
- 事前申込: 要
- 参加者数 (事前申込者数): 84 名