活動情報

イベント詳細

第29回セミナー・勉強会

日時: 2022.10.17 Mon. 10:00-12:00
会場: オンライン
話者: 垣村 尚徳(慶應義塾大学,C01班)
題目: 制約付きのオンライン二部マッチング
概要:
オンライン二部マッチング問題は,二部グラフの片側の頂点がひとつずつやってくるときに,できるだけ大きなサイズのマッチングを求める問題である.この問題は検索広告の割り当て,ライドシェアリング,クラウドソーシングなどさまざまな応用をもつ.本講演では,オンライン二部マッチングに,これらの応用を動機とした制約を課した問題を考え,定数競合比を達成するアルゴリズムを提案する.本講演は,澄田範奈氏,伊藤伸志氏,竹村慧氏,波多野大督氏,福永拓郎氏,河原林健一氏との共同研究に基づく.
2022.10.03 更新