Online Stochastic Weighted Matching: Improved Approximation Algorithms

Motivated by the display ad allocation problem on the Internet, we study the

online stochastic weighted matching

problem. In this problem, given an edge-weighted bipartite graph, nodes of one side arrive online i.i.d. according to a known probability distribution. Recently, a sequence of results by Feldman et. al [14] and Manshadi et. al [20] result in a 0.702-approximation algorithm for the unweighted version of this problem, aka

online stochastic matching

, breaking the 1 − 1 /

e

barrier. Those results, however, do no hold for the more general online stochastic weighted matching problem. Moreover, all of these results employ the idea of

power of two choices

.

In this paper, we present the first approximation (0.667-competitive) algorithm for the online stochastic weighted matching problem beating the 1 − 1 /

e

barrier. Moreover, we improve the approximation factor of the online stochastic matching by analyzing the more general framework of

power of multiple choices

. In particular, by computing a careful third pseudo-matching along with the two offline solutions, and using it in the online algorithm, we improve the approximation factor of the online stochastic matching for any bipartite graph to 0.7036.