Coincidencia ponderada en línea - Algoritmos aleatorios

Question

Vamos a considerar el problema de coincidencia en línea ponderado en línea.

Los vértices llegan en línea y revelan todos sus bordes actuales y pesos de borde $ w_e> 0 $ .El objetivo es maximizar el peso de las coincidencias.Un borde solo se puede agregar una vez e irrevocablemente a la coincidencia.Con la misma frecuencia, consideramos básicamente considerar la configuración de KVV.

es obvio, que cualquier algoritmo determinista no puede ser competitivo contra un adversario ajeno.Dado que cualquier borde nuevo podría tener un peso grande arbitrario.

¿Puede un algoritmo aleatorio mejorar este resultado?

Answer 1

Un algoritmo aleatorio no puede ser competitivo constante en el peor de los casos. Una prueba que utiliza el principio de Yao se puede encontrar aquí .