Corrispondente al limite superiore per problemi online

Question

Ho un problema online e voglio dimostrare che nessun algoritmo online deterministico è competitivo.

Permettere $ texttt {on} $ essere un algoritmo online e $ texttt {opt} $ Un algoritmo offline ottimale (un avversario). Data una sequenza di $ n $ Input $ sigma = sigma_1 sigma_2 cDots sigma_n $ rivelato in modo online, lascia $ v ( texttt {on} _ sigma) $ e $ v ( texttt {opt} _ sigma) $ essere i valori raggiunti rispettivamente da $ texttt {on} $ e $ texttt {opt} $.

Quello che ho dimostrato è questo: lascia $ sigma = sigma_1 sigma_2 $ essere una sequenza a 2-input. Se $ texttt {on} $ agisce su $ sigma_1 $ con azione $ a $, quindi ho potuto trovare un input $ sigma_2 $ tale che $$ frac {v ( texttt {opt} _ sigma)} {v ( texttt {on} _ sigma)}, $$ è illimitato.

Il problema è che, se l'azione $ a $ cambiamenti, quindi il rapporto sopra potrebbe essere uguale a $1$.

È sufficiente dimostrare che il rapporto è illimitato per qualche azione $ a $? O deve essere vero per qualsiasi $ a $?