加权在线匹配 - 随机算法

Question

让我们考虑边缘加权在线匹配问题。

顶点在线到达，并透露所有当前的边缘和边缘权重 $ w_e> 0 $ 。目标是最大化匹配权重。只能加入一下边缘并不可撤销地匹配。通常，我们认为基本上考虑从kvv的设置。

显而易见的是，任何确定性算法都不能对令人沮丧的对手竞争。由于任何新边缘都可以具有任意的大量重量。

可以改善此结果的随机算法吗？

Answer 1

随机算法不能在最坏情况下持续竞争。 使用姚明原则的证据可以找到在这里