Correspondance en ligne pondérée - algorithmes randomisés

Question

Considérons le problème de correspondance en ligne pondéré par le bord.

Les sommets arrivent en ligne et révèlent toutes leurs bords actuels et leurs poids de bord $ w_e> 0 $ .L'objectif est de maximiser le poids des assorties.Un bord ne peut être ajouté qu'une seule fois et irrévocablement à la correspondance.Comme souvent, nous considérons essentiellement de considérer le réglage de kvv.

Il est évident que tout algorithme déterministe ne peut être compétitif contre un adversaire inconscient.Puisque tout nouveau bord pouvait avoir un poids important arbitraire.

Un algorithme randomisé peut-il améliorer ce résultat?

Answer 1

Un algorithme randomisé ne peut pas être concurrentiel constant dans le pire des cas. Une preuve utilisant le principe de Yao peut être trouvée