1
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

Since we are dealing with deterministic algorithms, the adversary can pick the hardest input possible for the online algorithm.

Since the online algorithm we are discussing is deterministic, given some input, its output can always be determined. The adversary is 'smart' in the sense that they are able to look ahead and pick input such that it gives the worst possible result for the online algorithm.

What you have proved seems to be sufficient.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.