Seminars

View all Seminars  |  Download ICal for this event

Recent progress in online matching - General arrival models

Series: Theory Seminar

Speaker: Dr. Zhiyi Huang Associate Professor Department of Computer Science University of Hong Kong

Date/Time: Aug 06 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms.
<br>
This is the first of two talks that presents the basics of online matching, and surveys the recent progress in two directions. Todays talk will be focussing on General arrival models and for the next talk, we will look at some Open problems in online advertising.
<br>
General arrival models
<br>
Traditional online matching models consider bipartite graphs and assume knowing one side of the bipartite graph upfront. The matching problems in many modern scenarios, however, do not fit into the traditional models. In the problem of matching ride-sharing requests, for instance, the graph is not bipartite in general, and all vertices arrive online. There has been much progress in the past three years on online matching models beyond the traditional ones, including the fully online model, the general vertex arrival model, and the edge arrival model.
<br>
For more details about the seminar please visit the website at <a href="Link
<br>
Microsoft Teams Link:<br>
<a href="Link

Host Faculty: Dr. Arindam Khan