patternMinor
Weighted Online Matching - randomized algorithms
Viewed 0 times
weightedrandomizedalgorithmsonlinematching
Problem
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?
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?
Solution
A randomized algorithm cannot be constant-competitive in worst-case order.
A proof using Yao's principle can be found here.
A proof using Yao's principle can be found here.
Context
StackExchange Computer Science Q#128542, answer score: 4
Revisions (0)
No revisions yet.