29th CoRe Seminar
Date and time: | 2022.10.17 Mon. 10:00-12:00
|
---|---|
Venue: | Online |
Speaker: | KAKIMURA, Naonori (Keio U., Group C01) |
Title: | Constrained online bipartite matching |
Summary: | The online bipartite matching problem is the problem of finding a maximum-size matching when vertices on one side arrive one by one. The problem has practical applications such as online advertisement, ride-sharing, and crowd sourcing. This talk proposes a variant of the problem motivated by such applications, and presents online algorithms with constant competitive ratio. This talk is based on joint work with Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Ken-ichi Kawarabayashi.
|
Update:2022.10.03