Online Knapsack Problems with Estimates

Let such that $1/\epsilon \in 𝐍$, and let $k=\lfloor \frac{2}{1-2\delta }\rfloor$. Let us consider an arbitrary algorithm for the Oske problem. The following instance is announce as a prediction:

We do a full case distinction on the possible behaviors of the algorithm. The first item is presented as $\epsilon$.

The subsequent $1/\epsilon -1$ items are presented as $0$. The next item is revealed with size $p$. This is possible as $p+\delta \ge 1/2$, which follows from Equation (3).

All remaining items are presented as $1-p$, which the algorithm can not pack due to the $\epsilon$-item. As we have seen, it is possible that an item which was announced of size $1/2$ can be presented as $p$; therefore presenting those items as $1-p$ is possible as well due to the symmetry of the deviation.

An optimal solution can pack both, $p$ and its counterpart, while the algorithm has packed $p$ and an item of size $\epsilon$. The competitive ratio is then $1/p$ for $\epsilon$ converging to $0$.

The subsequent $k-1$ items will be presented as $p$ if the algorithm continues to reject them. If an algorithm should pack any of these items, we can use the same argumentation as in Case 1.1.

Should the algorithm reject all $k$ items of size $p$, the last item is presented as $1-p-2\delta$. The optimal solution consists of all $k$ items of size $p$, whereas the algorithm only has the item of size $\epsilon$ and the last item of size $1-2\delta -p$ in its knapsack. Since $1-p-2\delta \le p$ by Equation (3) and $kp/(1-p-2\delta )=1/p$ by Equation (2) is valid, the competitive ratio is at least $1/p$ for $\epsilon$ converging to $0$.

The subsequent $1/\epsilon -1$ items will be presented as $\epsilon$ if the algorithm continues to reject them. If the algorithm should pack any of these items, the remaining items are presented as $0$ and we use the same argumentation as in Case 1.

Should the algorithm reject all $1/\epsilon -1$ items of size $\epsilon$, the subsequent $k$ items will be presented as $p+\epsilon$. If such an item is packed, the argumentation is the same as in case 1.1, just with the difference that the optimal solution contains the $\epsilon$-items with a total size of $1$.

If no such item is packed, the last item is presented of size $1-2\delta -p\le p$ (see Equation (3)). The optimal solution packs the full knapsack using items of size $\epsilon$. Again, the competitive ratio is at least $\frac{1}{p}$. $◀$

The following theorem gives a better bound than Theorem 4 when happens. Note that $q>p$ is true for and the relation $\frac{3}{16}\in [\frac{1}{6},0.23]$ holds. Consequently, after Theorem 5, it remains to inspect the lower $q$-bound for .

Let $\delta \le \epsilon >0$ such that $1/\epsilon \in 𝐍$, let $k=\lceil \frac{2}{1-2\delta }\rceil$, and recall that $q=1-2\delta -1/k$. Let us consider an arbitrary algorithm for the Oske problem. The following prediction is announced to the algorithm:

We do a case distinction on the potential behaviors of the algorithm. The first item is presented as $\epsilon$.

The subsequent $1/\epsilon -1$ items are presented as $0$. The next presented item is of size $1/k$. This is possible if $2\delta \ge q$ since Equation (3) yields $q\ge 1/k$. The former holds for $\delta \ge 3/16$.

The remaining $k-1$ items are presented as $0$, with the last item presented as $1-1/k=q+2\delta$. An optimal solution can pack both $1/k$ and its counterpart, while the algorithm has packed $1/k$ and an item of size $\epsilon$. The competitive ratio is then $k$ for $\epsilon$ converging to $0$ which yields the wished ratio by $k\ge 1/q$ tanks to Equation (3).

The subsequent $k-1$ items will be presented as $1/k$, with the last item presented as $q$, if the algorithm continues to reject them. If an algorithm should pack any of these items, we can use the same argumentation as in Case 1.1.

The optimal solution consists of all $k$ items of size $1/k$, which add up to exactly $1$, whereas the algorithm only has the item of size $\epsilon$ and the last item $q$ in its knapsack. The competitive ratio is again at least $1/q$ for $\epsilon$ converging to $0$.

The subsequent $1/\epsilon -1$ items will be presented as $\epsilon$ as long as they get rejected. If an algorithm packs any of these items, we can use the same argumentation as in Case 1.

Should the algorithm reject all $1/\epsilon -1$ items of size $\epsilon$, the subsequent $k$ items will be presented as $0$. The last item is presented as $q$ which directly yields the competitive ratio of $1/q$. Here an optimal solution consists of a full knapsack with $\epsilon$ items. $◀$

The crucial issue of Theorem 5 for small $\delta$ are the items of announced size $\delta$, where an adversary must be able to present them as a $0$ or as $\frac{1}{3}$ for all . As this is not possible, we need to handle the setting as a special case. In particular, $q>p$ for is true, and since holds, starting with delta at $1/12$ is no limitation.

We define $a=\frac{1}{3}-2\delta$, and let $\epsilon >0$ be arbitrary such that $1/\epsilon \in 𝐍$ and $a/\epsilon \in 𝐍$ holds. Let us consider an arbitrary algorithm for the Oske problem. The algorithm receives the following prediction:

We do a similar full case distinction on the possible behaviors of the algorithm, like in Theorem 4 and Theorem 5. The first item is presented as $\epsilon$, but this time we stop presenting $\epsilon$-items when the algorithm has packed exactly an amount of $y$ between $a$ and $a+\epsilon$.

The subsequent $\epsilon$-items are presented as $0$. The next item is presented of size $1/3$.

The remaining $2$ items are presented as $\frac{2}{3}-a=\frac{1}{3}+2\delta$. An optimal solution can pack $1/3$ together with one large item and several $\epsilon$-items such that it achieves a packing of at least $1-\epsilon$, while the algorithm has packed $1/3$ and some $\epsilon$-items of total size less than $a+\epsilon$. The competitive ratio is then ${(2/3-2\delta )}^{-1}={(1-1/3-2\delta )}^{-1}=1/q$ for $\epsilon$ converging to $0$ which yields the wished competitive ratio.

The subsequent $2$ items will be presented as $1/3$ until one gets accepted. If an algorithm accepts one of the first two items, we can use the same argumentation as in Case 1.1.

Otherwise, the algorithm accepts the last $1/3$-item or none of them. The optimal solution consists of all $3$ items of size $1/3$, which add up to exactly $1$, whereas the algorithm again has only the $\epsilon$-items of total size $a+\epsilon$ and at most the last $1/3$ item in its knapsack. The calculation of the competitive ratio is analogous to case 1.1.

We presented all the $\epsilon$-items as $\epsilon$ and we know after these items that the algorithm got at most $y\le a$ in the knapsack.

Next, we start to reveal $1/3+(a-y)+\epsilon$ items. This is possible because of the relation

Should the algorithm pick one of these $3$ items, we are in the same setting as in case 1.1, but with an optimal solution consisting of just $\epsilon$-items. $◀$

As the construction of Theorem 5 cannot work for small $\delta$, it is also worth noting that the construction of Theorem 6 is not working for larger $\delta$. This is mainly because the items which are announced with size $\frac{1}{3}+\delta$ must be presented of size $\frac{1}{3}$ at least. Even if the $3$ would be replaced with some $k$, it would allow an algorithm to pack multiple of those items without a chance of an adversary to hinder him.

Finally, we see that the case $\delta \ge 0.5$ can be handled using a standard construction by Marchetti-Spaccamela and Vercellis [29], thus no algorithm can achieve a bounded competitive ratio here.

Consider an arbitrary algorithm and the prediction $P=(0.5,0.5)$. The first item arrives as $\epsilon >0$. If the algorithm rejects it, the second item arrives as 0. Otherwise, the second item arrives as $1-\epsilon /2$ so the algorithm cannot pack it, whereas the optimum solution can. This construction shows that no algorithm can be competitive. $◀$

Assume that there exists an announced item of size at least $0.5$. Then the algorithm waits for it, packs it, and achieves a gain of $0.5-\delta$, which gives us the claimed bound.

Thus, assume that such an item does not exists but that there exists an item that the algorithm cannot fit into its knapsack when packing greedily. This item can be at most of actual size $0.5+\delta$, meaning our gap due to not packing this item is at most $1-(0.5+\delta )=0.5-\delta$, which again gives us our wanted bound. $◀$

In the rest of this section, we will present a more refined algorithm and prove that it matches the lower bounds of Theorems 4 and 5. Let us fix an instance $(P,\delta )$, where holds, and $P=(x_1^{\prime },\mathrm{\dots },x_n^{\prime })$ are the announced item sizes of the Oske problem. As in Definition 1, if $x$ is an item, then $x^{\prime }$ denotes its announced size. Let $c=1/\min (p,q)$ and $\overline{c}=1/c$, see Equation (1) for the definition of $p$ and $q$.

It is easy to see that the algorithm achieves the desired competitive ratio in many instances.

First, suppose there is an item $x$ of announced size at least $\overline{c}+\delta$. In this case, $x$ is the only item packed, see line 2. Since $x\ge \overline{c}$ is true, the competitive ratio is ensured.

Second, suppose that all items have announced size at most $1-\overline{c}-\delta$. In this case, we pack greedily, see line 4. Let $x$ be the first item that cannot be packed by the algorithm; if $x$ does not exist, we have found the optimal solution. Otherwise, $x\le 1-\overline{c}$ holds, which means that we have packed more than $\overline{c}$ and the competitive ratio is also ensured. $◀$

For the rest of the section, suppose that the largest announced item is in $(1-\overline{c}-\delta ,\overline{c}+\delta )$, and let $x_l$ be the last announced item such that $x_l^{\prime }\in (1-\overline{c}-\delta ,\overline{c}+\delta )$. In this case, the algorithm can guarantee a packing of at least $\overline{c}$ for most instances. To see this, we classify each item $y$ as either tiny, small, medium or large depending on the actual size of $y$ and the sum of the already packed items when $y$ arrives. We use the substitutions $\mu :=\overline{c}-(x_l^{\prime }-\delta )$ and $\nu :=1-(x_l^{\prime }+\delta )$. To give an overview of the variables and relations we provide Figure 2.

Observe that before $x_l$ arrives, medium items are skipped by the algorithm, see line 13. The case when a small or large item arrives is handled by the following lemma.

Let $y$ be the first small or large item that arrives and let $m$ be the size of the packing when $y$ arrives. Since medium items are skipped, only tiny items were packed before $y$, which means .

First, suppose that $y$ is small. In this case, $y$ is packed and after that, the knapsacks packing is of size in $[\mu ,\nu ]$, which means that no item is packed until $x_l$ arrives because the condition on line 13 is satisfied. Observe that when $x_l$ arrives, the algorithm tries to pack it. Note that $m+y+x_l\le m+(\nu -m)+(x_l^{\prime }+\delta )=1$, which means that $x_l$ fits into the knapsack when it arrives. Now observe that after $x_l$ is packed, the knapsack has size at least $m+y+x_l\ge m+(\mu -m)+(x_l^{\prime }-\delta )=\overline{c}$, as required.

Second, suppose that $y$ is large. Note that since otherwise we would be in the case handled by Lemma 9.

Now observe that $m+y\le \mu +(\overline{c}+2\delta )=2\overline{c}-x_l^{\prime }+3\delta \le 2\overline{c}-(1-\delta -\overline{c})+3\delta =3\overline{c}+4\delta -1\le 3q+4\delta -1$, where the last inequality follows from $\overline{c}=\min (p,q)$. Now we expand the definition of $q$, see Equation (1):

Hence, $y$ fits into the knapsack. By Definition 10, $y+m\ge \overline{c}$ is valid, as required.

In both cases, the algorithm packs $y$ and can guarantee a packing of at least $\overline{c}$. $◀$

Recall that the instance of Oske we are solving is $(P,\delta )$. The following lemma says that we can assume that $x_l$ is the last item.

If all items after $x_l$ are packed, then the competitive ratio can only decrease. Suppose that an item $x$ comes after $x_l$ and is not packed. By choice of $x_l$, we know that $x^{\prime }\le 1-\overline{c}-\delta$, which means that $x\le 1-\overline{c}$. Hence, the algorithm has packed more than $\overline{c}$, and the competitive ratio is at most $c$. $◀$

By Lemma 11 and 12, we may assume that $x_l$ is the last item and all other items are either tiny or medium. We split the analysis into two cases depending on whether at most $\lfloor \frac{2}{1-2\delta }\rfloor$ non-tiny items are packed in an optimal solution.

Recall that the algorithm packs exactly the tiny items and $x_l$, which means we may assume that there are no tiny items (their presence would decrease the competitive ratio). Since $x_l\ge 1-\overline{c}-2\delta$ holds due to the choice of $x_l$, we may assume $x_l=1-\overline{c}-2\delta$ without decreasing the ratio. By Equation (3), $1-\overline{c}-2\delta \le \overline{c}$ is valid, since $\overline{c}=\min (p,q)$ is defined. Hence, each item is of size at most $\overline{c}$ and the ratio is at most $\frac{k\overline{c}}{1-\overline{c}-2\delta }$. By Equation (2), we have

Hence, the algorithm achieves a competitive ratio of $\frac{1}{p}$. This matches the lower bound given by Theorem 4 for the case $p\le q$. $◀$

For the other case, we can guarantee that the knapsack is filled with at least $\frac{1}{q}$.

Since at least $k$ non-tiny items are packed by an optimal solution, there is a non-tiny item of size at most $1/k$. First, suppose that there is a medium item $y\ne x_l$ such that $y\le 1/k$. Let $m$ be the size of the packed items immediately before $y$ arrives. Since $y$ is medium, we have $1/k+m\ge y+m>\nu$. Hence, after $x_l$ is packed, the algorithm has packed

which implies a competitive ratio of at most $1/q$.

The remaining case is $y>1/k$ for each medium item $y\ne x_l$ and $x_l\le 1/k$. Observe that

which is a contradiction since $x_l^{\prime }>1-\overline{c}-\delta$. Hence, this case cannot occur, and the algorithm achieves a competitive ratio of at most $\frac{1}{q}$. $◀$

With the previous observations, the following theorem immediately follows.

Let $\epsilon >0$ be small enough so that $x+2\epsilon \le x+\delta$ and $1-x-\epsilon \ge 1-x+\epsilon -\delta$. An arbitrary algorithm is given the following prediction:

The first two items presented are $1-x$ and $x+\epsilon$. The algorithm can pack either of these items but not both.

The third item is presented as $x$ and the last one as $1-x+\epsilon$. Since $x>0.5$, the algorithm can pack at most one item from the set $\{x,x+\epsilon ,1-x+\epsilon \}$ and its best choice is keeping $x+\epsilon$, whereas an optimal solution is to pack $x$ and $1-x$. Hence, the competitive ratio goes to $1/x$ as $\epsilon$ goes to 0.

The next item is presented as $x+2\epsilon$. Now the algorithm either keeps $1-x$ or discards it and packs $x+2\epsilon$.

The final item is presented as $1-x-\epsilon$. Since $x+2\epsilon \ge 1-x-\epsilon$, the algorithm can pack at most $x+2\epsilon$, whereas the optimal solution packs the full knapsack by taking $x+\epsilon$ and $1-x-\epsilon$. Hence, the competitive ratio goes to $1/x$ as $\epsilon$ goes to 0.

The final item is presented as small as possible and presented as $y:=1-x-2\delta +\epsilon$. Now the algorithm can pack at most $1-x+y$ whereas the optimal solution packs $x+2\epsilon +y$. Hence, the competitive ration goes to $(1-x+y)/(x+y)$ as $\epsilon$ goes to 0. By definition of $x$, we see that also, in this case, the algorithm cannot achieve a better competitive ratio than $\frac{1}{x}=c$. $◀$

Note that the construction of Theorem 16 will yield a bound of $\mathrm{\Phi }$ for $\delta =\frac{3}{4}-\frac{\sqrt{5}}{4}$, which can also be achieved without estimates as in Iwama and Taketomi [24].

First, suppose that $y$ is the first large item in the instance. Observe that the algorithm packs $y$ on line 4 and terminates. Since $y\ge x$, a competitive ratio of at least $1/x$ is achieved. From now on, suppose that there are no large items.

Second, suppose that there are two medium items $y_1$ and $y_2$ such that $y_1+y_2\le 1$. Observe that until $x_l$ arrives, if there is only one medium item packed, then it is the smallest medium item that has arrived so far (see line 12). Hence, there is an iteration of the while loop in which the condition on line 11 is satisfied, i.e., two medium items are packed and the algorithm terminates. Since $2(1-x)>x$ holds for $\delta >0$, the algorithm has again packed at least $x$ as required. From now on, suppose that no two medium items fit together, no matter their position in the instance.

Third, suppose there is a small item $a$ that is not part of the knapsack at the end, i.e., $a$ was ignored on line 5 or removed on line 8 or 12 before packing $y$. Let $m$ be the value in the knapsack at the end of the iteration in which $a$ is discarded, and observe that $m+a>1$ (otherwise $a$ would be packed, resp. not removed). Since $a\le 1-x$, we have $m>1-a\ge 1-(1-x)=x$. Hence, the algorithm has packed at least $x$ (and terminates in the next iteration, see line 3). From now on, we may assume that the algorithm packs all small items. In particular, if there is at most one medium item, the algorithm finds the optimal solution. Hence, assume that there are at least two medium items.

Observe that by definition of $x_l$, there are no medium items after $x_l$. Hence, when $x_l$ arrives, there is a medium item $y$ in the knapsack. Let $s$ be the size of all small items except for $x_l$ (note that $x_l$ is small or medium). Assume $x_l$ is small, i.e., the algorithm packs at least $x_l+(1-x)+s$. Since no two medium items fit together, an optimal solution packs at most $x_l+x+s$. Observe that $x_l\ge 1-x-\delta -\delta$, as it was announced with size at least $1-x-\delta$. Hence the competitive ratio is at most:

Finally, suppose that $x_l$ is medium. Observe that the algorithm packs $\max (y,x_l)+s>0.5+s$, as $y$ and $x_l$ combined exceed $1$. Since no two medium items fit together, an optimal solution packs at most $x+s$. Hence, the competitive ratio is at most as desired. $◀$

Again, if $\delta \le \frac{3}{4}-\frac{\sqrt{5}}{4}$, an optimal algorithm does not need to consider the estimates given.