1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Why would you fix the input beforehand? $\endgroup$ – Yuval Filmus Oct 13 '20 at 18:57
  • $\begingroup$ I read the following paper link.springer.com/article/10.1007/s00186-015-0526-9 and in theorem 1, the authors fixed a sequence than proved that any online algorithm will have a large competitive ratio. $\endgroup$ – zdm Oct 13 '20 at 18:59
  • $\begingroup$ It is very hard to prove an online lower bound if you fix the sequence in advance. In effect, by fixing the input you are revealing the input to the algorithm. $\endgroup$ – Yuval Filmus Oct 13 '20 at 19:03
  • $\begingroup$ So what I wrote actual proves that no deterministic algorithm exists for the defined knapsack problem? $\endgroup$ – zdm Oct 13 '20 at 19:05
  • $\begingroup$ The proof of Theorem 1 doesn't fix the sequence in advance. The sequence depends on the actions of the algorithm. It's true that all of these sequences are prefixes of a single sequence, but there's no such "requirement". $\endgroup$ – Yuval Filmus Oct 13 '20 at 19:06
2
$\begingroup$

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:

  1. 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.

$\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.