Basic
information about the project
| Project | Sample Complexity of Online Stochastic Matching |
|---|---|
| Group | FYP23077 |
| Student | Liu Xinyu (3035830648) |
| Supervisor | Huang Zhiyi |
Background
Online stochastic matching revolves around a bipartite graph G = (U, V, E), where the offline vertex set U is given upfront, and the vertices in the online vertex set V with their incident edge(s) in E together will arrive one by one.
The term “stochastic” indicates that the online vertices are i.i.d. from a known distribution.
Each online vertex v must be matched instantaneously and irrevocably when it arrives, and the decision is made according to the aim of maximizing the number of matches for the unweighted matching case.
Nevertheless, the underlying distribution of the online vertices may not be available in advance for general cases. Therefore, researchers started to get interested in the topic of sample complexity of the online stochastic matching problem.
The concept of sample complexity mainly discusses the number of samples that is sufficient for the algorithm to learn a good enough approximation.
The example of online advertising is one of the applications driving the exploration of online matching.
Search engines show sponsor ads alongside the search results that are customized to the user’s preferences.
The goal of advertisers is to show their ads to users who are most likely to be interested in their goods or services, while many advertisers may compete for the same user with a target keyword at one time.
Therefore, the search engine needs to immediately pick an advertiser when a search is performed.
But how the desicion should be made?