Matching Upper Bound for Online Problems
-
06-11-2019 - |
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