Online Stochastic Matching: Online Actions Based on Offline Statistics

摘要

We consider the online stochastic matching problem proposed by Feldman et al. Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 ? 1=e. Annual IEEE Sympos. Foundations Comput. Sci. 117-126 as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the number of allocations.