3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you familiar with KVV? $\endgroup$ – Yuval Filmus Jul 20 at 11:09
  • $\begingroup$ 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) $\endgroup$ – Felix Jul 20 at 11:11
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.