Weighted Online Matching. A randomized approach


Let’s consider the edge weighted online matching problem.

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?