  Online bipartite matching and its variants are among the most fundamental
problems in the online algorithms literature. Karp, Vazirani, and Vazirani
(STOC 1990) introduced an elegant algorithm for the unweighted problem that
achieves an optimal competitive ratio of $1-1/e$. Later, Aggarwal et al. (SODA
2011) generalized their algorithm and analysis to the vertex-weighted case.
Little is known, however, about the most general edge-weighted problem aside
from the trivial $1/2$-competitive greedy algorithm. In this paper, we present
the first online algorithm that breaks the long-standing $1/2$ barrier and
achieves a competitive ratio of at least $0.5086$. In light of the hardness
result of Kapralov, Post, and Vondr\'ak (SODA 2013) that restricts beating a
$1/2$ competitive ratio for the more general problem of monotone submodular
welfare maximization, our result can be seen as strong evidence that
edge-weighted bipartite matching is strictly easier than submodular welfare
maximization in the online setting.
  The main ingredient in our online matching algorithm is a novel subroutine
called online correlated selection (OCS), which takes a sequence of pairs of
vertices as input and selects one vertex from each pair. Instead of using a
fresh random bit to choose a vertex from each pair, the OCS negatively
correlates decisions across different pairs and provides a quantitative measure
on the level of correlation. We believe our OCS technique is of independent
interest and will find further applications in other online optimization
problems.
