SeminarsView 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
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.
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.
General arrival models
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.
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Microsoft Teams Link:
Host Faculty: Dr. Arindam Khan