Correspondant à la limite supérieure pour les problèmes en ligne

Question

J'ai un problème en ligne et je veux prouver qu'aucun algorithme en ligne déterministe n'est compétitif.

Laisser $ texttt {on} $ être un algorithme en ligne et $ texttt {opt} $ un algorithme hors ligne optimal (un adversaire). Étant donné une séquence de $ n $ contributions $ sigma = Sigma_1 Sigma_2 cdots Sigma_n $ révélé de manière en ligne, laissez $ v ( texttt {on} _ Sigma) $ et $ v ( texttt {opt} _ Sigma) $ être les valeurs obtenues respectivement par $ texttt {on} $ et $ texttt {opt} $.

Ce que j'ai prouvé, c'est le suivant: laissez $ Sigma = Sigma_1 Sigma_2 $ être une séquence à 2 entrées. Si $ texttt {on} $ agit sur $ Sigma_1 $ avec action $ a $, alors je pouvais trouver une entrée $ Sigma_2 $ tel que $$ frac {v ( texttt {opt} _ sigma)} {v ( texttt {on} _ sigma)}, $$ est sans limite.

Le problème est que, si l'action $ a $ changements, alors le rapport ci-dessus pourrait être égal à $1$.

Est-il suffisant pour prouver que le ratio est illimité pour une action $ a $? Ou doit-il être vrai pour tout $ a $?