Correspondência on-line ponderada - algoritmos randomizados

Question

Vamos considerar o problema de correspondência on-line ponderado da borda.

Os vértices chegam online e revelam todas as suas bordas atuais e pesos de borda $ w_e> 0 $ .O objetivo é maximizar o peso das correspondências.Uma borda só pode ser adicionada uma vez e irrevogavelmente para a correspondência.Como tantas vezes, consideramos basicamente considerar a configuração da KVV.

É óbvio que qualquer algoritmo determinístico não pode ser competitivo contra um adversário inconveniente.Como qualquer nova borda poderia ter grande peso arbitrário.

Pode um algoritmo randomizado melhorar neste resultado?

Answer 1

Um algoritmo randomizado não pode ser competitivo constante em ordem de pior caso. Uma prova usando o princípio de Yao pode ser encontrada aqui .