Corrispondenza online ponderata - Algoritmi randomizzati

Question

Consideriamo il problema di corrispondenza online ponderato del bordo.

I vertici arrivano online e rivelano tutti i loro bordi attuali e i loro pesi dei bordi $ w_e> 0 $ .L'obiettivo è massimizzare il peso delle corrispondenze.Un bordo può essere aggiunto solo una volta e irrevocabilmente alla corrispondenza.Come spesso, consideriamo fondamentalmente considerando l'impostazione da KVV.

È ovvio, che qualsiasi algoritmo deterministico non può essere competitivo contro un avversario ignaro.Poiché qualsiasi nuovo bordo potrebbe avere un peso arbitrario di grandi dimensioni.

può migliorare un algoritmo randomizzato su questo risultato?

Answer 1

Un algoritmo randomizzato non può essere competitivo costante nell'ordine del caso peggiore. Una prova che utilizza il principio di Yao può essere trovato Qui .