Pergunta

I have an online problem and I want to prove that no deterministic online algorithm is competitive.

Let $\texttt{ON}$ be an online algorithm and $\texttt{OPT}$ an optimal offline algorithm (an adversary). Given a sequence of $n$ inputs $\sigma=\sigma_1\sigma_2\cdots\sigma_n$ revealed in an online fashion, let $v(\texttt{ON}_\sigma)$ and $v(\texttt{OPT}_\sigma)$ be the values achieved respectively by $\texttt{ON}$ and $\texttt{OPT}$.

What I proved is this: let $\sigma=\sigma_1\sigma_2$ be an 2-input sequence. If $\texttt{ON}$ acts on $\sigma_1$ with action $a$, then I could find an input $\sigma_2$ such that $$\frac{v(\texttt{OPT}_\sigma)}{v(\texttt{ON}_\sigma)},$$ is unbounded.

The problem is that, if the action $a$ changes, then the above ratio could be equal to $1$.

Is it sufficient to prove that the ratio is unbounded for some action $a$? Or must it be true for any $a$?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top