Online Unweighted Knapsack Problem with Removal Cost

Abstract

In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u ₁,u ₂,…,u _n , each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u _i , we either put u _i into the knapsack or reject it with no cost. When u _i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u _i and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred.

In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible.

1 Introduction

The knapsack problem is one of the most classical problems in combinatorial optimization and has a lot of applications in the real world [11]. The knapsack problem is that: given a set of items with values and sizes, we are asked to maximize the total value of selected items in the knapsack satisfying the capacity constraint.

In this paper, we study the online version of the unweighted knapsack problem with removal cost. Here, “online” means (i) the information of the input (i.e., the items) is given gradually, i.e., after a decision is made on the current item, the next item is given; (ii) the decisions we have made are irrevocable, i.e., once a decision has been made, it cannot be changed. Given the ith item u _i , we either accept u _i (i.e., put u _i into the knapsack) or reject it with no cost. When u _i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u _i and the total size in the current knapsack exceeds 1, i.e., the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred.

1.1 Related Works

The online knapsack problem (under no removal condition) was first studied on average case analysis by Marchetti-Spaccamela and Vercellis [13]. They proposed a linear time approximation algorithm such that the expected difference between the optimal profit and the one obtained by the algorithm is O(log^3/2 n) under the condition that the capacity of the knapsack grows proportionally to the number of items n. Lueker [12] improved the expected difference to O(logn) under a fairly general condition on the distribution.

Iwama and Taketomi [9] studied the online knapsack problem on worst case analysis. They obtained a $\frac{1+\sqrt{5}}{2}\approx1.618$-competitive algorithm for the online knapsack when (a) the removable condition (without removal cost) is allowed and (b) the value of each item is equal to the size (unweighted), and showed that this is best possible by providing a lower bound 1.618 for the case. We remark that the problem has unbounded competitive ratio, if at least one of the conditions (a) and (b) is not satisfied [9, 10]. For other models such as minimum knapsack problem and knapsack problem with limited cuts, refer to papers in [7, 8, 14].

The concept of removal costs was introduced in the buyback problem [1–6]. In the problem, we observe a sequence of bids and decide whether to accept each bid at the moment it arrives, subject to constraints on accepted bids such as single item and matroid constraints. Decisions to reject bids are irrevocable, whereas decisions to accept bids may be canceled at a cost which is a fixed fraction of the bid value. Babaioff et al. [3] showed that the buyback problem with matroid constraint has $(1+2f+2\sqrt{f(1+f)} )$-competitive ratio, where f>0 is a buyback factor. Ashwinkumar [1] extended their results and show that the buyback problem with the constraint of k matroid intersections has $k(1+f)(1+\sqrt{1-\frac{1}{k(1+f)}})^{2}$-competitive ratio. Babaioff et al. [3, 4] also studied the buyback problem with (weighted) knapsack constraints. They show that if the largest item is of size at most γ, where 0<γ<1/2, then the competitive ratio is $(1+2f+2\sqrt{f(1+f)})/(1-2\gamma)$.

1.2 Our Results

In this paper, we study the worst case analysis of the online unweighted knapsack problem with removal cost. We consider two kinds of models of removal cost:the proportional and the unit cost models. In the proportional cost model, the removal cost of each item u _i is proportional to its value (and hence size), i.e., it is f⋅s(u _i ), where s(u _i ) denotes the size of u _i and f>0 is a fixed constant, called buyback factor. Therefore, we can view this model as the buyback problem with knapsack constraints. In the unit cost model, the removal cost of each item is a fixed constant c>0, where we assume that every item has value at least c, since in many applications, the removal cost (i.e., cancellation charge) is not higher than its value. We remark that the problem has unbounded competitive ratio if no such assumption is satisfied (see Sect. 3).

We show that the proportional and unit cost models have competitive ratios λ(f) and μ(c) in (1) and (2), respectively, where λ(f) and μ(c) are given in Figs. 1 and 2. Namely, we construct λ(f)- and μ(c)-competitive algorithms for the models and prove that they are best possible.

$$\begin{aligned} \lambda(f) =& \begin{cases} 2 &(1/2\ge f>0),\\ \frac{1+f+\sqrt{f^2+2f+5}}{2} &(f>1/2), \end{cases} \end{aligned}$$

(1)

$$\begin{aligned} \mu(c) =& \begin{cases} \max\{\eta(k),\xi(k+1) \}&(1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt {\frac{k}{k+1}},k=1,2,\dots),\\ \xi(1)&(1-\frac{1}{\sqrt{2}}\le c\le1/2),\\ 1/c &(c\ge1/2), \end{cases} \end{aligned}$$

(2)

where

$$\begin{aligned} \eta(k)=\frac{k(c+1)+\sqrt {k^2(1-c)^2+4k}}{2k(1-kc)}\quad \text{and}\quad \xi(k)=\frac{1}{2}+ \frac{1}{2}\sqrt{1+\frac{4}{kc}}. \end{aligned}$$

(3)

Fig. 1

The competitive ratio λ(f) for the proportional cost model

Fig. 2

The competitive ratio μ(c) for the unit cost model

The main ideas of our algorithms for both models are:

• We may reject items (with no cost) many times, but in at most one round, we remove items which from the knapsack.

• Some items are removed from the knapsack, only when the total value in the resulting knapsack gets high enough to guarantee the optimal competitive ratio.

The rest of the paper is organized as follows. In the next section, we consider the proportional cost model, and in Sect. 3, we consider the unit cost model.

2 Proportional Cost Model

In this section, we consider the proportional cost model, where each item u _i has removal cost f⋅s(u _i ) for some positive constant f. We first show that λ(f) is a lower bound of the competitive ratio of the problem, and then propose a λ(f)-competitive algorithm, where λ(f) is given in (1).

2.1 Lower Bound

In this subsection, we show a lower bound of the competitive ratio λ(f) for the problem.

Theorem 1

There is no online algorithm with competitive ratio less than λ(f) for the online unweighted knapsack problem with proportional removal cost.

Proof

According to the value of f, we separately consider the following two cases.

Case 1: 1/2≥f>0. Let A denote an online algorithm chosen arbitrarily. For a sufficiently small ε(>0), our adversary (see Fig. 3) requests the sequence of items whose sizes are

$$\begin{aligned} \frac{1}{2}+\varepsilon,\frac{1}{2}+ \frac{\varepsilon}{2}, \dots, \frac{1}{2}+\frac{\varepsilon }{\lceil1/f\rceil+1}, \end{aligned}$$

(4)

until A rejects some item in (4). If A rejects the item with size $\frac{1}{2}+\varepsilon$, then the adversary stops the input sequence. On the other hand, if it rejects the item with size $\frac{1}{2}+\frac {\varepsilon}{k}$ for some k>1, then the adversary requests an item with size $\frac{1}{2}-\frac {\varepsilon}{k}$ and stops the input sequence.

Fig. 3

The adversary for the case 1/2≥f>0

We first note that algorithm A must take the first item, since otherwise the competitive ratio of A becomes infinite. After the first round, A always keeps exactly one item in the knapsack, since all the items in (4) have size larger than $\frac {1}{2}$ (i.e., a half of the knapsack capacity) and for any j<k we have $(\frac{1}{2}+\frac{\varepsilon}{j})+ (\frac{1}{2}-\frac{\varepsilon }{k})$ is larger than 1. This implies that A removes the old item from the knapsack to accept a new item. If A rejects $\frac{1}{2}+\frac{\varepsilon}{k}$ for some k>1, the competitive ratio is at least $1/ (\frac{1}{2}+\frac{\varepsilon }{k} )$, which approaches 2(=λ(f)) as ε→0. Finally, if A rejects no item in (4), then its profit is

$$\begin{aligned} \frac{1}{2}+\frac{\varepsilon}{\lceil1/f\rceil+1}-f\sum_{k=1}^{\lceil 1/f\rceil} \biggl(\frac{1}{2}+\frac{\varepsilon}{k} \biggr) \le\frac{1}{2}-f\sum _{i=1}^{\lceil1/f\rceil}\frac{1}{2} \le0 \end{aligned}$$

(5)

while the optimal profit for the offline problem is $\frac{1}{2}+ \varepsilon$, which completes the proof for 1/2≥f>0.

Case 2: f>1/2. Let A denote an online algorithm chosen arbitrarily, and let $x=\frac{3+f-\sqrt{f^{2}+2f+5}}{2(1+f)}$. For a sufficiently small ε(>0), our adversary requests the following sequence of items

$$\begin{aligned} x,1-x+\varepsilon,1-x, \end{aligned}$$

(6)

until A rejects some item in (6), and if A rejects the item then the adversary immediately stops the input sequence. We remark that x<1/3 for f>1/2, and the second and third items do not fit in the knapsack together.

Note that A must accept the first item x, since otherwise the competitive ratio becomes infinite. If A rejects the second item, then the competitive ratio is at least

$$\begin{aligned} \frac{1-x+\varepsilon}{x}\ge\frac{1-x}{x} =\lambda(f). \end{aligned}$$

(7)

If A takes the second item 1−x+ε (and removes the first item), the competitive ratio is at least $\frac{1}{1-x+\varepsilon-f\cdot x}$ since the second and third items do not in the knapsack together, which approaches to $\lambda(f)(= \frac{1}{1-x-f\cdot x})$ as ε→0, which completes the proof for f>1/2. □

2.2 Upper Bound

In this subsection, we show Algorithm 1 is λ(f)-competitive for the problem. Note that the total profit becomes small (even negative), if we remove many items from the knapsack. Intuitively, our algorithm accepts the new item if the knapsack has room to put it. If we can make the profit sufficiently high by accepting the item and removing some items from the current knapsack, then our algorithm follows this, and after this iteration, it rejects all the items. Otherwise, the algorithm simply rejects the item.

Algorithm 1

An online algorithm for proportional cost model

Let u _i be the item given in the ith round. Define by B _i−1 the set of items in the knapsack at the beginning of ith round, and by s(B _i−1) the total size in B _i−1.

Lemma 2

If s(B _i−1)+s(u _i )>1 and some $B_{i-1}'\subseteq B_{i-1}$ satisfies $\lambda(f)\cdot s(B_{i-1})< s(B_{i-1}')+s(u_{i})\le1$, then the sixth line of Algorithm 1 is executed in the i th round.

Proof

Since s(B _i−1)+s(u _i )>1 and $\lambda(f)\cdot s(B_{i-1})< s(B_{i-1}')+s(u_{i})$, we obtain

$$\begin{aligned} &\frac{1}{\lambda(f)}+f\cdot\bigl(s(B_{i-1})-s\bigl(B_{i-1}' \bigr)\bigr) \\ &{}< \frac{s(B_{i-1})+s(u_i)}{\lambda(f)}+f\cdot\bigl(s(B_{i-1})-s\bigl(B_{i-1}' \bigr)\bigr) \\ &{}<\frac{1+f\lambda(f)-f\lambda^2(f)}{\lambda^2(f)}s\bigl(B_{i-1}'\bigr)+ \frac{1+f\lambda(f)+\lambda(f)}{\lambda^2(f)}s(u_i). \end{aligned}$$

(8)

As λ ²(f)≥1+fλ(f)+λ(f) by the definition of λ(f), we have

$$\begin{aligned} &\frac{1+f\lambda(f)-f\lambda^2(f)}{\lambda^2(f)}\le\frac{1+f\lambda (f)-f\lambda^2(f)}{1+f\lambda(f)+\lambda(f)}<1 \quad\text{and}\\ &\frac{1+f\lambda(f)+\lambda(f)}{\lambda^2(f)}\le1. \end{aligned}$$

 □

Let OPT denote an optimal solution for the offline problem whose input sequence is u ₁,…,u _i .

Lemma 3

If s(B _i )<1/λ(f) then we have |OPT∖B _i |≤1.

Proof

B _i contains all the items smaller than 1/2 seen so far, since s(B _i )<1/λ(f)≤1/2. Any item u∈OPT∖B _i has size greater than 1−1/λ(f)≥1/2. Therefore, |OPT∖B _i |≤1 holds by s(OPT)≤1. □

Theorem 4

The online Algorithm 1 is λ(f)-competitive.

Proof

Suppose that the sixth line is executed in round k. Then it holds that $\frac{1}{\lambda(f)}+f\cdot (s(B_{k-1})-s(B_{k-1}'))< s(B_{k-1}')+s(u_{k})=s(B_{k})$. Since s(B _i )=s(B _k ) holds for all i≥k, we have

$$\begin{aligned} \frac{s(\mathrm {OPT})}{s(B_i)-f\cdot(s(B_{k-1})-s(B_{k-1}'))} \le\frac {1}{s(B_k)-f\cdot(s(B_{k-1})-s(B_{k-1}'))}<\lambda(f). \end{aligned}$$

We next assume that the sixth line has never been executed. If s(B _i )≥1/λ(f), we have the competitive ratio s(OPT)/s(B _i )≤1/s(B _i )≤λ(f). On the other hand, if s(B _i )<1/λ(f), |OPT∖B _i |=0 or 1 holds by Lemma 3. If |OPT∖B _i |=0, we obtain the competitive ratio 1. Otherwise (i.e., OPT∖B _i ={u _l } for some l), Lemma 2 implies that $\lambda(f)\cdot s(B_{l-1})\ge s(B_{l-1}')+s(u_{l})$ for $B_{l-1}'=\mathrm {OPT}\cap B_{l-1}$. Therefore we obtain

$$\begin{aligned} \frac{s(\mathrm {OPT})}{s(B_i)} \le&\frac{s(B_{l-1}')+s(u_l)+s(B_i\setminus B_{l-1})}{s(B_{l-1})+s(B_i\setminus B_{l-1})} \\ \le&\max\biggl\{ \frac{s(B_{l-1}')+s(u_l)}{s(B_{l-1})}, \frac {s(B_i\setminus B_{l-1})}{s(B_i\setminus B_{l-1})} \biggr\} \le \lambda(f). \end{aligned}$$

 □

Before concluding this section, we remark that the condition in the sixth line can be checked efficiently.

Proposition 5

We can check the condition in the sixth line in $O(|B_{i-1}|+2^{\lambda ^{2}(f)})$ time.

Proof

Let $x=\frac{1}{1+f} (\frac{1}{\lambda(f)}+f s(B_{i-1})-s(u_{i}) )$ and y=1−s(u _i ). Our goal is to decide whether there exists $B_{i-1}'\subseteq B_{i-1}$ such that $x<s(B_{i-1}')\le y$ in $O(|B_{i-1}|+2^{\lambda^{2}(f)})$ time. As s(B _i−1)<1/λ(f), s(u _i )≤1, and λ ²(f)≥(1+f)λ(f)+1 by the definition of λ(f), we get

$$\begin{aligned} y-x =&1-\frac{1}{\lambda(f)(1+f)}-\frac{f}{1+f}\bigl(s(u_i)+s(B_{i-1}) \bigr) \\ >& 1-\frac{1}{\lambda(f)(1+f)}-\frac{f}{1+f}\biggl(1+\frac{1}{\lambda (f)}\biggr) \\ =& \frac{\lambda(f)-1-f}{\lambda(f)(1+f)} \ge\frac{\lambda(f)}{\lambda ^2(f)-1}-\frac{1}{\lambda(f)} = \frac{1}{\lambda^3(f)-\lambda(f)}\ge\frac{1}{\lambda^3(f)}. \end{aligned}$$

(9)

Let B _i−1={b ₁,b ₂,…,b _m } satisfy s(b ₁)≥…≥s(b _k )≥y−x>s(b _k+1)≥…≥s(b _m ). Then we claim the existence of $B_{i-1}'$ is equivalent to the existence of A⊆{b ₁,b ₂,…,b _k } such that $x-\sum_{i=k+1}^{m} s(b_{i})< s(A)\le y$. If such an A exists, then $B_{i-1}'=A\cup\{b_{k+1},\dots,b_{l}\}$ satisfies the conditions, where $l=\min\{l\ge k+1\mid s(A)+\sum_{i=k+1}^{l} s(b_{i})>x\}$. If there exists $B_{i-1}'$ such that $x<s(B_{i-1}')\le y$, then $A=B_{i-1}'\setminus\{b_{k+1},\dots,b_{m}\}$ satisfies $x-\sum_{i=k+1}^{m} s(b_{i})< s(A)\le y$.

Therefore we need to check the condition $x-\sum_{i=k+1}^{m} s(b_{i})< s(A)\le y$ for at most $2^{k}<2^{\lambda^{2}(f)}$ subsets, since k≤s(B _i−1)/(y−x)<λ ²(f) holds by s(B _i−1)<1/λ(f) and y−x>1/λ ³(f). Thus we can check the condition in the sixth line in $O(|B_{i-1}|+2^{\lambda^{2}(f)})$. □

3 Unit Cost Model

In this section, we consider the unit cost model, where it costs us a fixed constant c>0 to remove each item from the knapsack. Recall that every item has size at least c. In this section, we show that the online unweighted knapsack problem with unit cost is μ(c)-competitive, where μ(c) is defined in (2). We note that μ(c) attains the maximum $1+\sqrt{2}$ when $c=1-1/\sqrt{2}$.

We remark that the problem becomes unbounded competitive ratio if items are allowed to have size arbitrarily smaller than c.

Lemma 6

For any positive number r, there is no online algorithm with competitive ratio less than r for the knapsack problem with unit removal cost without the size assumption.

Proof

Let ε denote a positive number such that ε<1/(⌈1/c⌉⋅r). For an online algorithm A chosen arbitrarily, our adversary (see Fig. 4) keeps requesting the items with size ε, until A accepts ⌈1/c⌉ items or rejects r⋅⌈1/c⌉ items. If A rejects r⋅⌈1/c⌉ items (before accepting ⌈1/c⌉ items), the adversary stops the input sequence; otherwise, it requests an item with size 1 and stops the input sequence. In the former case, the competitive ratio is at least $\frac{ r \lceil1/c\rceil \varepsilon}{\lceil1/c\rceil\varepsilon}=r$. In the latter case, the competitive ratio becomes $\frac{1}{\lceil1/c\rceil\cdot\varepsilon}> r$ if A rejects the last item (with size 1). Otherwise, A removes the ⌈1/c⌉ items to take the last item. This implies that the profit is 1−⌈1/c⌉⋅c≤0.

Fig. 4

An input sequence to prove the competitive ratio is unbounded if the input contains items with size smaller than c

 □

3.1 The Case c≥1/2

We first consider the case where c≥1/2. In this case, it is not difficult to see that the problem is 1/c(=μ(c))-competitive.

Theorem 7

If the unit removal cost c is at least 1/2, then there is no online algorithm with competitive ratio less than 1/c for the online unweighted knapsack problem.

Proof

For an online algorithm A chosen arbitrarily, our adversary first requests an item with size c. If A does not accept it, the adversary stops the input sequence. Otherwise, it next requests an item with size 1 and stops the input sequence. It is clear that A must take the first item, since otherwise the competitive ratio becomes infinite. If A rejects the second item, then we have the competitive ratio 1/c. Otherwise (i.e., A accepts the second item by removing the first item), the competitive ratio is 1/(1−c)≥1/c, since c≥1/2. □

Theorem 8

There is a 1/c-competitive algorithm for the online unweighted knapsack problem with unit removal cost.

Proof

Consider an online algorithm which takes the first item u ₁ and rejects the remaining items. Since s(u ₁)≥c and the optimal value of the offline problem is at most 1, the competitive ratio is at most 1/c. □

3.2 The Case c<1/2

In this section we consider the case in which c<1/2.

3.2.1 Lower Bound

For 0<c<1/2, we show that μ(c) is a lower bound of the competitive ratio for the problem by starting with several propositions needed later.

Proposition 9

For any positive integer k, we have

$$\begin{aligned} \frac{1}{2k+4}<1-\sqrt{\frac{k+1}{k+2}}\quad \text{and}\quad 1-\sqrt{ \frac{k}{k+1}}<\frac{1}{2k+1}. \end{aligned}$$

(10)

Proof

Note that

$$\begin{aligned} 1-\sqrt{\frac{k+1}{k+2}}=\frac{\sqrt{k+2}-\sqrt{k+1}}{\sqrt{k+2}} =&\frac{1}{\sqrt{k+2}(\sqrt{k+2}+\sqrt{k+1})} \\ >&\frac{1}{\sqrt{k+2}(\sqrt{k+2}+\sqrt{k+2})}=\frac{1}{2k+4}, \end{aligned}$$

(11)

and

$$\begin{aligned} 1-\sqrt{\frac{k}{k+1}}=\frac{\sqrt{k+1}-\sqrt{k}}{\sqrt{k+1}} =&\frac {1}{\sqrt{k+1}(\sqrt{k+1}+\sqrt{k})} \\ =&\frac{1}{k+1+\sqrt{k(k+1)}}<\frac{1}{2k+1}. \end{aligned}$$

(12)

 □

Definition 10

We define x _k and y _k as follows:

$$\begin{aligned} x_k=\frac{k+2-kc-\sqrt{k^2(1-c)^2+4k}}{2}\quad \text{and}\quad y_k= \frac{kc+\sqrt{k^2c^2+4kc}}{2}. \end{aligned}$$

(13)

Proposition 11

η(k) and ξ(k) in (3) satisfy the following equalities.

$$\begin{aligned} \eta(k) =&\frac{1}{1-x_k-kc}=\frac{1-x_k}{kx_k}=\frac{k(c+1)+\sqrt {k^2(1-c)^2+4k}}{2k(1-kc)}, \end{aligned}$$

(14)

$$\begin{aligned} \xi(k) =&\frac{1}{y_k-kc}=\frac{y_k}{kc}=\frac{1}{2}+ \frac{1}{2}\sqrt{1+\frac{4}{kc}}. \end{aligned}$$

(15)

We provide two kinds of adversaries.

Theorem 12

Assume that removal cost c satisfies $1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$ for a positive integer k. Then there is no online algorithm with competitive ratio less than η(k) for the online unweighted knapsack problem with unit removal cost.

Proof

Let $x_{k}=\frac{k+2-kc-\sqrt{k^{2}(1-c)^{2}+4k}}{2}$. For an online algorithm A chosen arbitrarily, our adversary (see Fig. 5) keeps requesting the items with size x _k until A accepts k items or rejects ⌈1/x _k ⌉ items. If A rejects ⌈1/x _k ⌉ items before accepting k items, the adversary stops the input sequence (a). Otherwise (i.e., A accepts k items), the adversary next requests an item with size 1−x _k +ε where ε is a sufficiently small positive number; if A rejects it, the adversary stops the input sequence (b), and otherwise, the adversary next requests an item with size 1−x _k and stops the input sequence (c). Note that all the items have size at least c, since $1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$ implies x _k ≥c and 1−x _k ≥c.

Fig. 5

The adversary for Lemma 12

In the case of (a), we have the competitive ratio at least $\frac{1-x_{k}}{(k-1)x_{k}} > \frac{1-x_{k}}{kx_{k}}=\eta(k),$ where the last equality follows from Proposition 11. In the case of (b), the competitive ratio is at least $\frac{1-x_{k}+\varepsilon}{kx_{k}}> \frac{1-x_{k}}{kx_{k}} =\eta(k)$ by Proposition 11. Finally, in the case of (c), the competitive ratio is at least $\frac{1}{1-x_{k}+\varepsilon-kc}$. Proposition 11 implies that this approaches $\eta(k) (=\frac{1}{1-x_{k}-kc})$ as (ε→0). □

Theorem 13

Assume that removal cost c satisfies $1-\sqrt{\frac{k}{k+1}}\le c < \frac{1}{2k}$ for a positive integer k. Then there is no online algorithm with competitive ratio less than ξ(k) for the online unweighted knapsack problem with unit removal cost.

Proof

Let A denote an online algorithm chosen arbitrarily. Then our adversary (see Fig. 6) keeps requesting items with size c until A accepts k items or rejects ⌈1/c⌉ items. If A rejects ⌈1/c⌉ items before accepting k items, the adversary stops the input sequence (a). Otherwise (i.e., A accepts k items), the adversary requests an item with size $y_{k}=\frac{kc+\sqrt{k^{2}c^{2}+4kc}}{2}$ which is at least 1−c>c, since $1-\sqrt{\frac{k}{k+1}}\le c < \frac{1}{2k}$; if A rejects it, the adversary stops the input sequence (b), and otherwise, the adversary requests an item with size 1−c and stops the input sequence (c).

Fig. 6

The adversary for Lemma 13

In the case of (a), the competitive ratio is at least $\frac {1-c}{(k-1)c}\ge\frac{1}{kc}\ge\frac{y_{k}}{kc}=\xi(k)$, where the last equality follows from Proposition 11. In the case of (b), the competitive ratio is $\frac{y_{k}}{kc}=\xi (k)$ by Proposition 11. Finally, in the case of (c), the competitive ratio is at least $\frac{1}{y_{k}-kc}=\xi(k)$, which again follows from Proposition 11. □

By Theorems 12 and 13, it holds that μ(c) is a lower bound of the competitive ratio for 0<c<1/2.

3.2.2 Upper Bound

In this subsection, we show that μ(c) is also an upper bound for the competitive ratio of the problem when 0<c<1/2. We start with several propositions needed later.

Proposition 14

For a positive integer k, let c satisfy $1-\sqrt{\frac {k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$. Then we have

$$\begin{aligned} \eta(k)\ge2\quad \iff&\quad c\ge\frac{2k-1}{2k(2k+1)}, \end{aligned}$$

(16)

$$\begin{aligned} \xi(k+1)\ge2\quad \iff&\quad c\le\frac{1}{2(k+1)}. \end{aligned}$$

(17)

Proof

We can get the results by simple calculations. □

Proposition 15

For a positive integer k, let c satisfy $1-\sqrt{\frac {k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$. Then we have

$$\begin{aligned} \mu(c)=\max\bigl\{\eta(k),\xi(k+1) \bigr\}\ge2. \end{aligned}$$

(18)

Proof

If $\frac{2k-1}{2k(2k+1)}\le c\le1-\sqrt{\frac{k}{k+1}}$ then by (16), the claim is correct. Otherwise (i.e., $c< \frac{2k-1}{2k(2k+1)}<\frac{1}{2(k+1)}$), we also have (18) by (17). □

Proposition 16

For a positive integer k, let c satisfy $1-\sqrt{\frac {k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$. Then we have

$$\begin{aligned} \max\Bigl\{ \max_{\alpha\in\{1,2,\dots,k\}}\eta(\alpha),\xi(k+1) \Bigr\} =\max \bigl\{\eta(k),\xi(k+1) \bigr\}=\mu(c). \end{aligned}$$

(19)

Proof

The second equality holds by the definition of μ(c). Thus we only need to prove the first equality.

For α≥2, it holds that

$$\begin{aligned} 1-\sqrt{\frac{\alpha+1}{\alpha+2}}< \frac{2\alpha-1}{2\alpha(2\alpha+1)} \end{aligned}$$

(20)

since $1-\sqrt{\frac{\alpha+1}{\alpha+2}}< \frac{2\alpha-1}{2\alpha(2\alpha+1)} \iff12\alpha^{2}(\alpha-2)+2\alpha(6\alpha-1)+(\alpha-2)>0$.

If k>α≥2, then it holds

$$\begin{aligned} \eta(\alpha)= \frac{\alpha(c+1)+\sqrt{\alpha^2(1-c)^2+4\alpha}}{2\alpha (1-\alpha c)} < 2\le\mu(c) \end{aligned}$$

(21)

by $c\le1-\sqrt{\frac{k}{k+1}}\le1-\sqrt{\frac{\alpha+1}{\alpha+2}}< \frac{2\alpha-1}{2\alpha(2\alpha+1)}$ and Proposition 14.

Moreover when α=1, we have

$$\begin{aligned} \eta(1)=\frac{(c+1)+\sqrt{(1-c)^2+4}}{2(1-c)}\le2\le\mu(c) \end{aligned}$$

(22)

for 0<c≤1/6 since $\frac{(c+1)+\sqrt{(1-c)^{2}+4}}{2(1-c)}\le 2\iff(1-6c)(1-c)\ge0$. As $1-\sqrt{3/4}<1/6<1-\sqrt{2/3}$, we remain to prove η(1)≤η(2) for $1/6\le c<1-\sqrt{2/3}$. By $c<1-\sqrt{2/3}< 1/2$,

$$\begin{aligned} &\frac{c+1+\sqrt{(1-c)^2+4}}{2(1-c)}\le\frac{2(c+1)+\sqrt {4(1-c)^2+8}}{4(1-2c)}\\ &\quad\Longleftarrow\quad\frac{c+1+\sqrt{(1-c)^2+4}}{(1-c)}\le\frac{(c+1)+\sqrt {(1-1/2)^2+2}}{(1-2c)} \\ &\quad\Longleftrightarrow\quad(6c-1)(1-c)\bigl\{(4c-5)^2+63\bigr\}\ge0. \end{aligned}$$

 □

Proposition 17

For a positive integer k, let c satisfy $1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$. Then for any positive integer α≤k and real x∈(0,1−αc), it holds that

$$\begin{aligned} \min\biggl\{\frac{1}{1-x-\alpha c}, \frac{1-x}{\alpha x} \biggr\}\le \eta(\alpha) \le\mu(c). \end{aligned}$$

(23)

Proof

Since $\frac{1}{1-x-\alpha c}$ and $\frac{1-x}{\alpha x}$ are respectively monotone increasing and decreasing in x, the first inequality holds by Proposition 11. The second inequality is obtained by Proposition 16. □

Proposition 18

For a positive integer k, let c satisfy $1-\sqrt{\frac {k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$. Then for any real y∈((k+1)c,1], we have

$$\begin{aligned} \min\biggl\{\frac{1}{y-(k+1) c},\frac{y}{(k+1) c} \biggr\}\le\xi (k+1)\le \mu(c). \end{aligned}$$

(24)

Proof

Since $\frac{1}{y-(k+1)c}$ and $\frac{y}{(k+1)c}$ are respectively monotone decreasing and increasing in y, the first inequality holds by Proposition 11. The second inequality follows from the definition of μ(c). □

We are now ready to prove that μ(c) is an upper bound for the competitive ratio. According to the size of c, we make use of Algorithms 2 and 3.

Algorithm 2

An online algorithm for unit cost model with $c \ge (1 - \frac{1}{\sqrt{2}})$

Algorithm 3

An online algorithm for unit cost model with $c < (1 - \frac{1}{\sqrt{2}})$

For $1-\frac{1}{\sqrt{2}}\le c\le\frac{1}{2}$, we use Algorithm 2, where B _i−1 denotes the set of items in the knapsack at the beginning of the ith round Let u _i be the item given in the ith round. In this case, the profit of any two items is sufficiently high. Intuitively, our algorithm accepts the item if the knapsack has room to put it. If there is only one item in the knapsack and the new item has sufficiently high value, the algorithm accepts the new item and removes the item in the knapsack, and after this iteration, it rejects all the items. Otherwise, it simply rejects the item.

Theorem 19

If $1-\frac{1}{\sqrt{2}}\le c\le\frac{1}{2}$, the online Algorithm 2 is μ(c)-competitive for the online unweighted knapsack problem with unit removal cost.

Proof

Let OPT denote an optimal solution for the offline problem whose input sequence is u ₁,…,u _i . If the algorithm stops at the fourth line, the competitive ratio is at most $1/ (\frac{c+\sqrt{c^{2}+4c}}{2}-c )=\frac{c+\sqrt{c^{2}+4c}}{2c} =\mu(c)$, since s(OPT)≤1. Assume that the algorithm has never stopped at the fourth line and |B _i |=1. If s(B _i )≥1/2, then the competitive ratio is at most $\frac{1}{1/2}=2\le\mu(c)$. Otherwise, the item in B _i has size smaller than 1/2, while the item u _j with j<i and u _j ∉B _i has size at least 1/2. This implies that |OPT|=1 and the competitive ratio is smaller than μ(c), since s(B _i )≥c and $s(\mathrm {OPT})< \frac{c+\sqrt{c^{2}+4c}}{2}$. If the algorithm has never stopped at the fourth line and |B _i |>1, the competitive ratio is at most $\frac{1}{2c}< \mu(c)$, since $c\ge1-1/\sqrt{2}> 1/6$ implies $c+\sqrt{c^{2}+4c}> 1$. □

For $1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$ (k=1,2,…), we use Algorithm 3. Intuitively, our algorithm accepts the new item if the knapsack has room to put it. If we can make the profit sufficiently high by accepting the item and removing some items from the current knapsack by greedy manner, then our algorithm follows this, and after this iteration, it rejects all the items. Otherwise, the algorithm simply rejects the item.

Theorem 20

If $1-\sqrt{\frac{k+1}{k+2}}\le c\le1-\sqrt{\frac{k}{k+1}}$, the online Algorithm 3 is μ(c)-competitive for the online unweighted knapsack problem with unit removal cost.

Proof

Let OPT denote an optimal solution for the offline problem whose input sequence is u ₁,…,u _i . If the algorithm stops at the eleventh line in round l≤i, $s(B_{i})=s(B_{l})=s(B_{l-1}')+s(u_{l})$ and the profit of the algorithm is $s(B_{l-1}')+s(u_{l})-|B_{l-1}\setminus B_{l-1}'|c$. Therefore, the competitive ratio is at most $\frac {1}{s(B_{l-1}')+s(u_{l})-|B_{l-1}\setminus B_{l-1}'|c}\le\mu(c)$, since s(OPT)≤1. Otherwise, the algorithm has never removed old items from the knapsack. If s(B _i )≥1/2, then the competitive ratio is at most $\frac{1}{1/2}=2\le\mu(c)$. On the other hand, if s(B _i )<1/2, then any item in B _i has size at most 1/2 while any item in OPT∖B _i has size larger than 1/2. This implies |OPT∖B _i |≤1 by s(OPT)≤1. If |OPT∖B _i |=0, then we have OPT=B _i , which implies that the competitive ratio is 1. Thus we assume that |OPT∖B _i |=1. Note that |B _i |≤k+1 holds, since any b∈B _i satisfies $s(b)\ge c\ge1-\sqrt{\frac {k+1}{k+2}}\ge\frac{1}{2k+4}$, where the last inequality follows from Proposition 9. Since the algorithm has never removed items, |B _l |≤k+1 also holds for each l with l≤i. Let

$$\begin{aligned} \{u_l\}=\mathrm {OPT}\setminus B_i,\qquad \alpha=\big|B_{l-1}\setminus B_{l-1}'\big|,\qquad x=1- \bigl(s(u_l)+s\bigl(B_{l-1}'\bigr)\bigr). \end{aligned}$$

(25)

Since $B_{l-1}\setminus B_{l-1}'\neq\emptyset$, we have

$$\begin{aligned} \alpha>0 \quad \mbox{and}\quad x < 1-\alpha c. \end{aligned}$$

(26)

Since s(B _i )=s(B _l−1)+s(B _i ∖B _l−1) and s(OPT)≤s(u _l )+s(B _l−1∩OPT)+s(B _i ∖B _l−1), the competitive ratio is at most

$$\begin{aligned} \frac{s(u_l)+s(B_{l-1}\cap \mathrm {OPT})+s(B_i\setminus B_{l-1})}{s(B_{l-1})+s(B_i\setminus B_{l-1})} \le\max\biggl\{ \frac {s(u_l)+s(B_{l-1}\cap \mathrm {OPT})}{s(B_{l-1})}, 1 \biggr\}. \end{aligned}$$

We claim that $\frac{s(u_{l})+s(B_{l-1}\cap \mathrm {OPT})}{s(B_{l-1})} \leq\mu(c)$.

Let B _l ={b ₁,b ₂,…,b _m } satisfy s(b ₁)≥s(b ₂)≥…≥s(b _m ). To see this claim, we separately consider the following two cases:

Case 1. Consider the case in which there exists $b_{j}\in B_{l-1}'$ such that $b_{h}\notin B_{l-1}'$ holds for some h>j. Let us take b _j as the largest such item, i.e., $b_{j}\in B_{l-1}'$ and $b_{g}\notin B_{l-1}'$ for all g(<j).

In this case, we obtain the following inequalities:

$$\begin{aligned} \frac{s(u_l)+s(B_{l-1}\cap \mathrm {OPT})}{s(B_{l-1})} \le\frac {s(b_h)+1-x}{s(b_h)+\alpha x} \le\max\biggl\{1, \frac{1-x}{\alpha x} \biggr\}. \end{aligned}$$

(27)

Here the numerator and denominator in the left hand side of (27) respectively satisfy $s(u_{l})+s(B_{l-1}\cap \mathrm {OPT})\le1< s(b_{h})+s(u_{l})+s(B_{l-1}')=s(b_{h})+1-x$ and $s(B_{l-1})=s(B_{l-1}')+s(B_{l-1}\setminus B_{l-1}')\ge s(b_{h})+\alpha x$, since $b_{h}\notin B_{l-1}'$ and s(b)>x holds for any $b\in B_{l-1}\setminus B_{l-1}'$. Finally, we show $\frac{1-x}{\alpha x}\le\mu(c)$, which completes the claim.

Since the algorithm has not stopped at the eleventh line and 1−x−αc>0 by (26), we have $\frac{1}{1-x-\alpha c}=\frac{1}{s(B_{l-1}')+s(u_{l})-\alpha c}>\mu(c)$. Note that α≤|B _l−1∖{b _h }|≤k, since |B _l−1|≤k+1. Therefore, we obtain $\frac{1-x}{\alpha x}\le\mu(c)$ by Proposition 17.

Case 2. We next consider the case in which $b_{j}\in B_{l-1}'$ implies $b_{h}\in B_{l-1}'$ for all h(>j), i.e., $B_{l-1}'$ consists of the $|B_{l-1}'|$ smallest items of B _l−1. Then we have s(b)>1−s(u _l ) for any $b \in B_{l-1} \setminus B_{l-1}'$. This implies $B_{l-1}\cap \mathrm {OPT}\subseteq B_{l-1}'$, and $s(B_{l-1}\setminus B_{l-1}')> \alpha x$ holds by (25).

If α≤k, thus, the competitive ratio is at most

$$\begin{aligned} \frac{s(u_l)+s(B_{l-1}\cap \mathrm {OPT})}{s(B_{l-1})} \le\frac {s(u_l)+s(B_{l-1}')}{s(B_{l-1}\setminus B_{l-1}')} \le\frac {1-x}{\alpha x}\le\mu(c), \end{aligned}$$

(28)

where the last inequality follows from a similar argument to Case 1. On the other hand, if α=k+1, let $y=s(u_{l})+s(B_{l-1}')$. Then we have

$$\begin{aligned} \frac{s(u_l)+s(B_{l-1}\cap \mathrm {OPT})}{s(B_{l-1})}\le\frac{y}{(k+1)c}, \end{aligned}$$

(29)

where the inequality follows from the fact that $s(u_{l})+s(B_{l-1}\cap \mathrm {OPT})\le s(u_{l})+s(B_{l-1}')=y$ and $s(B_{l-1})\ge s(B_{l-1}\setminus B_{l-1}')\ge(k+1)c$, since $B_{l-1}\cap \mathrm {OPT}\subseteq B_{l-1}'$ and any item has size at least c. Finally, since y>(k+1)c and the algorithm has not stopped at the eleventh line, it holds that $\frac{1}{y-(k+1) c}=\frac{1}{s(B_{l-1}')+s(u_{l})-(k+1) c}>\mu(c)$. This together with Proposition 18 implies $\frac{y}{(k+1) c}\le\mu(c)$. □