# Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem.

The Vertices arrive online and reveal all their current edges and edge-weights $$w_e>0$$. The goal is to maximize the matchings weight. An edge can only be added once and irrevocably to the matching. As so often, we consider basically consider the setting from KVV.

It is obvious, that any deterministic algorithm can't be competitive against an oblivious adversary. Since any new edge could have arbitrary large weight.

Can a randomized algorithm improve upon this result?

• Are you familiar with KVV? Jul 20 '20 at 11:09
• Sorry for this. The Vertices arrive Online and reveal all their current edges and edge-weights $w_e>0$. And the goal is to maximize the matchings weight. An edge can only be added once and irrevocably to the matching. I am familiar with KVVs Ranking algorithm (for unweighted onesided bipartite graphs) Jul 20 '20 at 11:11

## 1 Answer

A randomized algorithm cannot be constant-competitive in worst-case order. A proof using Yao's principle can be found here.