Weighted Online Matching - randomized algorithms

Question

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?

Answer 1

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