View all Seminars  |  Download ICal for this event

Recent progress in online matching - Some open problems in online advertising

Series: Theory Seminar

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

Date/Time: Aug 13 11:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

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 second of two talks which presents the basics of online matching. The first talk focussed on General arrival models and todays talk will be looking at some Open problems in online advertising.
Open problems in online advertising:
AdWords and Display Ads are generalizations of the online bipartite matching problem by Karp et al. These problems capture online advertising which generates tens of billions of US dollars annually. This year, we introduce a new technique called online correlated selection, and design the first online algorithms for the general cases of AdWords and Display Ads outperforming greedy, which has remained the state of the art for more than 10 years, despite many attempts to find better alternatives.
For more details about the seminar please visit the website at
Microsoft Teams Link:

Speaker Bio:

Host Faculty: Dr. Arindam Khan