How to prove that knapsack has no competitive algorithm

Question

In online knapsack problem, items arrive one by one. Each time an item $i$ arrives, its weight $w_i$ is revealed. We would like to maximize, in an online fashion, the number of items placed in a bin of capacity $W$.

The proposition that I am trying to prove is that no deterministic competitive algorithm exists for this problem.

I did something like this: assume that an online algorithm decided to place an item $j$. Then the adversary can choose a sequence of items in a way that the online algorithm places only a single item. In other words, it chooses the sequence where $w_j=W$ and all other items have $w_i$ small enough to make the competitive ratio grows without bound.

This proof seems wrong because I did not fix the sequence of input beforehand, right? (My input sequence changes when the online algorithm changes.) I should fix the input, then prove that no online algorithm is competitive. How to do this?

Answer 1

Let's check the definition of a competitive algorithm, in your specific case. For simplicity, we assume that $W = 1$.

We can describe an algorithm for Knapsack as a sequence of functions $A_n\colon \mathbb{R}_+^n \to \{0,1\}^n$, describing which items are taken given their weights, which satisfies the following two properties:

1. The result fits inside the knapsack: for all $w \in \mathbb{R}_+^n$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i w_i \leq 1$.
2. The algorithm is online: for all $w \in \mathbb{R}_+^n$ and $m \leq n$, if $x = A_n(w)$ and $y = A_m(w_1,\ldots,w_m)$ then $x_i = y_i$ for $i = 1,\ldots,m$.

The algorithm is furthermore $c$-competitive if:

3. For all $w \in \mathbb{R}_+^n$ and $o \in \{0,1\}^n$ such that $\sum_{i=1}^n o_i w_i \leq 1$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i \geq c \sum_{i=1}^n o_i$.

(Your definition might put $c$ on the other side of the inequality.)

---

Suppose now that $A$ is a $c$-competitive algorithm, where $c > 0$, and let $N = \lceil 1/c \rceil + 1$, so that $cN > 1$.

Consider $w_1 = 1$ and $o_1 = 1$, which satisfies $o_1 w_1 = 1$. By Property 3, $x_1 = A_1(w_1)$ satisfies $x_1 \geq co_1 = c > 0$, and so necessarily $x_1 = 1$.

Now consider $w = 1,1/N,\ldots,1/N$, where there are $N$ many $1/N$'s, and $o = 0,1\ldots,1$, where there are $N$ many $1$'s. These vectors satisfy $\sum_{i=1}^{N+1} o_i w_i = 1$. Let $x = A_{N+1}(w)$. By Property 2, $x_1 = A_1(w_1) = 1$. By Property 1, $x_2 = \cdots = x_{N+1} = 0$. By Property 3, $$1 = \sum_{i=1}^{N+1} x_i \geq c\sum_{i=1}^{N+1} o_i = cN, $$ which contradicts the choice of $N$. This contradiction shows that no $c$-competitive algorithm exists.

---

Here is how this proof would usually be presented. Consider any competitive algorithm. We start by presenting it an item of weight $1$. If the algorithm doesn't take the item, then we immediately end the stream, and so the algorithm is revealed to be $0$-competitive (comparing to the solution which does take the item). Otherwise, we present it $N$ more elements of weight $1/N$. The algorithm's knapsack is already full, so it cannot take them. Since instead it could have taken only the $N$ low-weight elements, this shows that the algorithm isn't even $1/N$ competitive. Since $1/N$ can be arbitrary small, we reach a contradiction.

Notice how this argument is much less formal and much more "intuitive", if not particularly shorter (though this is only an artifact of this particular argument being so simple). We usually present it in the latter form, keeping in mind that we could translate it in principle to the more formal form of the former proof. This is no different than the difference between written proof and completely formal proof in the sense of formal logic.