Information

Event Records

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