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