# Online Weighted Matching: Beating the $\frac{1}{2}$ Barrier

Research paper by **Morteza Zadimoghaddam**

Indexed on: **18 Apr '17**Published on: **18 Apr '17**Published in: **arXiv - Computer Science - Data Structures and Algorithms**

#### Abstract

We study the problem of online weighted bipartite matching in which we want
to find a maximum weighted matching between two sets of entities, e.g. matching
impressions in online media to advertisers. Karp et al. designed the elegant
algorithm Ranking with competitive ratio $1-\frac{1}{e}$ for the unweighted
case. Without the commonly accepted Free Disposal assumption, it is easy to
show that no competitive ratio can be achieved in the weighted case. However,
under this assumption, it is not hard to show that algorithm Greedy is
$\frac{1}{2}$ competitive, and this is tight for deterministic algorithms.
After more than 25 years from the seminal work of Karp et al., it is still an
open question whether an online algorithm with competitive ratio better than
$\frac{1}{2}$ exists or not. We answer this question affirmatively by
presenting randomized algorithm $\mathsf{StochasticGreedy}$ with competitive
ratio greater than $0.501$. We also optimize this algorithm and propose
slightly changed algorithm $\mathsf{OptimizedStochasticGreedy}$ with
competitive ratio greater than $0.5018$.
In light of the hardness result of Kapralov et al. that restricts beating the
$\frac{1}{2}$-competitive ratio for Monotone Submodular Welfare Maximization
problem, our result can be seen as an evidence that solving weighted matching
problem is strictly easier than submodular welfare maximization in online
settings.