In this work, we prove the following lower bounds on the performance of online algorithms:

• •

  A lower bound of $1.2287$ on the competitive ratio for deterministic algorithms for either the proportional or the unit case of the removable knapsack problem, improving upon the previous bounds of $\frac{8}{7}\approx 1.14$ [9] and $\frac{7}{6}\approx 1.17$ [1] respectively,

• •

  A lower bound of $1.2$ on the competitive ratio for randomized algorithms for the proportional case of the removable knapsack problem, also improving upon the previous bound of $\frac{8}{7}\approx 1.14$ [9],

• •

  A lower bound of $1.2691$ on the asymptotic competitive ratio for randomized algorithms for the minimum peak appointment scheduling problem, improving upon the previous bound of $1.2$ [20].

We also consider some special cases for the online removable knapsack problem. For example, our results improve the known lower bound for three bins and deterministic algorithms.

Those of our lower bounds that are designed specifically for deterministic algorithms employ the “adaptive item sizing” technique [5], which we now describe. This approach and more advanced approaches (in particular, one where there is a multiplicative gap between sizes) were used for other online bin packing problems [13, 4, 3].

This is a procedure in which a sequence $S$ of items arrives, all with sizes in a predetermined interval $[\alpha,\beta]$, where $\alpha$ and $\beta$ are parameters. This allows the items from $S$ to be partitioned into a set of smallish items with sizes in the interval $[\alpha,\theta)$ and largish items with sizes in the interval $(\theta,\beta]$. The threshold $\theta$ satisfies $\alpha<\theta<\beta$, and the classification of each item as either smallish or largish occurs immediately after its packing by the deterministic algorithm, but the value of $\theta$ is determined later.

Such classification and partitioning can be ensured by a procedure resembling the binary search. Let $a$ and $b$ be variables such that $\alpha\leq a<b\leq\beta$. All items thus far classified as smallish have sizes in $[\alpha,\ a]$, and all items thus far classified as largish have sizes in $[b,\ \beta]$. Initially, we let $a=\alpha$ and $b=\beta$. Then, the next item to arrive can have any size in $(a,b)$, e.g., $\frac{a+b}{2}$. Once it is dealt with (packed or rejected) by the algorithm, and hence classified as either smallish or largish, the value of $a$ or $b$ respectively is set to this item’s size. Once all items in $S$ are processed, $\theta$ can take any value that could be the size of a next item in the sequence and thus separates the sizes of smallish and largish items, e.g., $\theta=\frac{a+b}{2}$ for the final values of the variables $a$ and $b$.

We start with a deterministic lower bound.

Proof. We focus on the proportional case, and remark that the proof also applies to the unit case because all items in the strategy have sizes that deviate from $\frac{1}{2}$ only by negligible amounts.

The input consists of two phases. The first phase employs the adaptive sizing framework for $k$ items, with $\frac{1}{2}-\upvarepsilon<\alpha<\beta<\frac{1}{2}$ for arbitrarily small $\upvarepsilon>0$. As there are $k$ bins, the algorithm is lazy, and item sizes are slightly below $\frac{1}{2}$, every item will be packed upon arrival (though possibly causing removal of another item), every non-empty bin at all times will contain either one or two items, and the number of items in any bin cannot decrease over item. The items are classified as follows upon packing: The first item to be placed in a bin is largish, the second one to be placed in a bin is smallish, and an item that replaces another inherits the replaced item’s class.

As a result, at the end of the first phase, each bin has at most two items, if is it non-empty, then it contains one largish item, and if it contains another one, then that item is smallish. Let $\Gamma$ denote the number of bins with two items, where $\Gamma\leq\lfloor\frac{k}{2}\rfloor$, since $k$ items were presented. If $\Gamma=0$, there are no smallish items, but the threshold $\theta$ is still well defined.

In the second phase, there are two possible continuations of the input, and the adversary’s choice depends on $\Gamma$. The first one, applied when $\Gamma$ is suitably large, is to issue $k$ items of size $1-\beta>\frac{1}{2}$ each. Since all previous items have sizes at most $\beta$, the optimal offline solution packs these items in pairs, and its profit is at least $k\cdot(\frac{1}{2}-\upvarepsilon)+k\cdot(1-\beta)>k\cdot(1-\upvarepsilon)$. Now consider the algorithm’s packing. As each item in the second phase has size strictly larger than $\frac{1}{2}$, any bin that was empty at the beginning of this phase, may contain at most one item at its end. The number of bins for the algorithm with exactly one item before the arrival of the new items is at most $k-2\cdot\Gamma$, and therefore the profit of the algorithm is below

$$(1-\beta)\cdot(k+\Gamma+(k-2\cdot\Gamma))<(\frac{1}{2}+\upvarepsilon)\cdot(2k-\Gamma)\ .$$

For $\upvarepsilon\to 0$, the competitive ratio in this case tends to $\frac{2k}{2k-\Gamma}$.

The other strategy for the second phase, applied when $\Gamma$ is suitably small, is to issue $\Gamma+\lfloor\frac{k-\Gamma}{2}\rfloor$ items of size $1-\theta$. Each such item has size slightly above $\frac{1}{2}$, and can be packed together with a smallish item but not with a largish item. Clearly, no bin can have more than one such item. Note that the number of smallish items in the input is at least $\Gamma$, and thus the number of largish items is at most $k-\Gamma$, because exactly $k$ items were issued in the first phase. It is possible that the number of smallish items is larger than $\Gamma$ if the algorithm removed a smallish item to pack another, which is then smallish as well. Offline, it is possible to pack $\Gamma$ bins by placing one smallish item together with one of size $1-\theta$ in each bin, $\lfloor\frac{k-\Gamma}{2}\rfloor$ bins with the remaining items of size $1-\theta$, one per bin, and packing all the now remaining items, i.e., largish and yet unpacked smallish ones in pairs into $\lceil\frac{k-\Gamma}{2}\rceil$ bins; note that if $k-\Gamma$ is odd, one of those last bins will contain only a single item. Again assuming that $\upvarepsilon\to 0$, in the limit the total size of items packed this way is

$$\Gamma+\frac{1}{2}\left\lfloor\frac{k-\Gamma}{2}\right\rfloor+\left\lfloor\frac{k-\Gamma}{2}\right\rfloor+\frac{1}{2}(k-\Gamma\mod 2)\ .$$

For the online algorithm, an item of size $1-\theta$ cannot be added to a bin with only a single item, since such item is largish by the adaptive item sizing used by the adversary. So the algorithm has only $\Gamma$ bins with total size approximately $1$, and its profit is approximately $\frac{k+\Gamma}{2}$ (up to negligible terms). Routine inspection of the cases of odd and even $k-\Gamma$ yields that the competitive ratio is at least

$$\frac{3k+\Gamma-(k-\Gamma\mod 2)}{2k+2\Gamma}\ .$$

If $\Gamma\geq k\cdot\frac{\sqrt{33}-5}{2}$, we have $\frac{2k}{2k-\Gamma}\geq 0.75+\sqrt{33}/12\approx 1.228713$, and otherwise, $\frac{3k+\Gamma}{2k+2\Gamma}\geq 0.75+\sqrt{33}/12\approx 1.228713$. Since for large $k$, the fraction $\frac{1}{2k+2\Gamma}\leq\frac{1}{2k}$ tends to zero, the lower bound follows.

In the cases $k=2,3,4,5,6,7,8,9,10$ we get:

$$\frac{4}{3},\ \frac{5}{4},\ \frac{6}{5},\ \frac{5}{4},\ \frac{5}{4},\ \frac{11}{9},\ \frac{16}{13},\ \frac{5}{4},\mbox{ \ and \ }\frac{16}{13}\ ,$$

by testing all values of $0\leq\Gamma\leq\lfloor\frac{k}{2}\rfloor$, the bounds of the first case and the suitable bound for the second case.

Again, we note that as all items have sizes almost equal to $\frac{1}{2}$, the proofs works also for unit profits (where these profits are approximately twice as large as the proportional profits).   

In this section we provide an alternative easier construction, which in general provides weaker bounds, though with the exception of two values of $k$, for which it improves the result of Theorem 2.1 (which was for deterministic online algorithms). Unlike that theorem, this one applies to randomized algorithms as well. Another difference is that here the input sequence is not “accommodating”, i.e., the optimal offline solution does not always pack all the items. The advantages of this construction are that it is fairly simple, and that it provides a lower bound for the case of randomized online algorithms.

Proof. Let $\upvarepsilon>0$ be a very small constant. The input starts with $2k$ items of each of the two sizes: $\frac{2}{3}-\upvarepsilon$, $\frac{1}{3}+3\upvarepsilon$. Since items are removable, and since there are sufficiently many items, we can assume that every bin will either have one item of size $\frac{2}{3}-\upvarepsilon$ or two items of sizes $\frac{1}{3}+3\upvarepsilon$.

Let $X$ be the expected number of bins with one item of size $\frac{2}{3}-\upvarepsilon$. The input continues in one of two ways. The first one is $k$ items of sizes $\frac{1}{3}+\upvarepsilon$, and the second one is $k$ items of sizes $\frac{2}{3}-3\upvarepsilon$. The optimal offline solution has $k$ full bins in either case. Consider the online algorithm. In the first case, its best approach is to add one item to each bin with an item of size $\frac{2}{3}-\upvarepsilon$. These bins are full, so there is no better packing for them. For each bin of the other kind, even if some replacements are made, the total size of the items it holds is at most $\frac{2}{3}+6\upvarepsilon$. By linearity of expectation, the expected profit of the algorithm is $k-\frac{k-X}{3}$ (letting $\upvarepsilon$ tend to zero and neglecting those terms).

In the other case, there is no reason for the algorithm to replace items of size approximately $\frac{2}{3}$. (Besides, such replacements change only the negligible $\upvarepsilon$ terms.) Every bin without such an item can become full when the algorithm replaces one item of size $\frac{1}{3}+3\upvarepsilon$ with the item of size $\frac{2}{3}-3\upvarepsilon$). The expected profit of the algorithm is $k-\frac{X}{3}$.

The threshold for $X$ is $\frac{k}{2}$. The first input is used if $X\leq\frac{k}{2}$, and the second one is used otherwise, if $X>\frac{k}{2}$. The competitive ratio is at least $1.2$.

For odd values of $k$, in the deterministic case we can use the integrality of $X$. The first input is used if $X\leq\frac{k-1}{2}$, and the second one is used otherwise, i.e., for $X\geq\frac{k+1}{2}$. The ratio is at least

$$\frac{k}{k-\frac{k+1}{6}}=\frac{6k}{5k-1}>1.2\ .$$

For $k=3,5,7,9$ we get lower bounds of $\frac{9}{7}$, $1.25$, $\frac{21}{17}$, and $\frac{27}{22}$, which improves slightly upon the lower bound from Theorem 2.1 for $k=3$ and $k=7$.   

We start with a simple construction for deterministic algorithms that uses the adaptive item sizing technique. Afterwards, we improve it into a lower bound for randomized algorithms.

Proof. The input consists of one or two phases, depending on the algorithm. In the first phase, for sufficiently large $N>0$, $12N$ items arrive with sizes chosen adaptively using $\alpha=\frac{1}{3}-2\upvarepsilon$ and $\beta=\frac{1}{3}-\upvarepsilon$ for an arbitrarily small value $\upvarepsilon>0$. We define the partition into smallish and largish items now. Those items whose intervals after packing contain the point $\frac{1}{2}$ are classified as smallish, and the remaining items (whose intervals do not contain the point $\frac{1}{2}$) are classified as largish. Recall that the adaptive sizing guarantees that there exists a threshold $\theta\in(\alpha,\beta)$ such that smallish items have sizes in $[\alpha,\theta)$ and largish items have sizes in $(\theta,\beta]$. Let $Q$ denote the number of smallish items.

We further classify the largish items as either “low” or ”high”, depending on whether their intervals lie completely to the left or to the right of the point $\frac{1}{2}$, if the positions are defined on the horizontal axis. Note that all high items contain the point $\frac{3}{4}$ in their intervals and similarly all low items contain the point $\frac{1}{4}$. If $Q\geq 5N$ or $Q\leq 2N$, then a solution that distributes the items evenly, i.e., places $4N$ items in each of the intervals

$$\left[0,\frac{1}{3}\right),\mbox{ \ \ \ \ }\left[\frac{1}{3},\frac{2}{3}\right),\mbox{ \ \ \ \ }\left[\frac{2}{3},1\right)\ ,$$

and thus has cost of $4N$, proves that the algorithm’s competitive ratio is at least $\frac{5}{4}$: For $Q\geq 5N$, there are $Q\geq 5N$ smallish items, all containing the point $\frac{1}{2}$, whereas for $Q\leq 2N$, there are must be at least $5N$ low or at least $5N$ high items (by the pigeonhole principle), which then all contain the point $\frac{1}{4}$ or $\frac{3}{4}$ respectively. Otherwise, when $Q\in(2N,5N)$, there is a second phase, which depends on $Q$’s relation to $3N$.

If $Q\geq 3N$, $12N$ items of size $\frac{2}{3}$ each are issued. An optimal offline solution places the first phase items in the interval $[0,\frac{1}{3})$, and it places the second phase $12N$ items in the interval $[\frac{1}{3},1)$, yielding optimal cost of $12N$. For the algorithm, all $12N$ second phase items must have the point $\frac{1}{2}$ as an internal point of their intervals, as do the $Q$ smallish items, so the cost of the algorithm is at least $15N$. Thus the asymptotic competitive ratio is at least $1.25$ in this case.

Finally, if $Q\leq 3N$, $Q^{\prime}$ items of size $1-\theta$ are issued, where $Q^{\prime}$ is divisible by $3$ and $Q-2\leq Q^{\prime}\leq Q$. Note that all low items have the point $\theta$ as an internal point of their intervals, and similarly, all high items have the point $1-\theta$ as an internal point. We find that the second phase items have a common point with every interval of the low and high items from the first phase. By the pigeonhole principle, there are at least $\frac{12N-Q}{2}$ low items or at least this many high items. Thus, for at least one of the points $\theta$ and $1-\theta$, there are at least $\frac{12N-Q}{2}+Q^{\prime}$ items whose intervals contain it, for a cost of at least $\frac{12N+Q^{\prime}}{2}-1$ for the algorithm. An optimal offline solution has $Q^{\prime}$ intervals of $[0,\theta)$ for smallish items, $Q^{\prime}$ intervals of $[\theta,1)$ for items of size $1-\theta$, and for the remaining $12N-Q^{\prime}$ items (where this number is divisible by $3$) there are $4N-\frac{Q^{\prime}}{3}$ intervals of every form out of $[0,\frac{1}{3})$, $[\frac{1}{3},\frac{2}{3})$, $[\frac{2}{3},1)$. Note that all smallish items have sizes not exceeding $\theta$, and the intervals assigned to such items by an optimal offline solution are sometimes slightly too long (because they have lengths of $\theta$).

The cost of an optimal offline solution is therefore at most $\frac{12N+2Q^{\prime}}{3}$. For large value of $N$, we can neglect the additive term and find a lower bound on the ratio

$$\frac{(12N+Q^{\prime})/2}{(12N+2Q^{\prime})/3}$$

for $Q^{\prime}\leq Q<3N$. This ratio is indeed at least $\frac{5}{4}$ for $Q^{\prime}<3N$ since

$$\frac{3(12+\frac{Q^{\prime}}{N})}{2(12+2\frac{Q^{\prime}}{N})}$$

is a monotonically decreasing function of $\frac{Q^{\prime}}{N}$, and for $Q^{\prime}\leq 3N$ it is minimized for $\frac{Q^{\prime}}{N}=3$, in which case

$$\frac{(12N+Q^{\prime})/2}{(12N+2Q^{\prime})/3}=1.25\ .$$

As in each of the four cases analyzed in the proof, the competitive ratio is at least $1.25$, possibly in the limit as $N$ grows to infinity, $1.25$ is a lower bound on asymptotic competitive ratio.   

Now, instead of using an adaptive classification of items, we show how to use very small items instead. This construction, which yields a superior bound, also applies to randomized algorithms.

Proof. Let $N,M>0$ be large integers, such that $N$ is even, and $M$ is divisible by $N!$.

To prove the lower bound for randomized algorithms, we use Yao’s approach, where one considers the best deterministic online algorithm for a known probability distribution over inputs.

Each input starts with a fixed prefix of $N\cdot M$ items of size $\frac{1}{N}$ each. For every point $z$ such that $0\leq z<1$, define $f(z)$ to be the number of items whose assigned intervals contain the point $z$ as an interior point or the left endpoint of the interval. Since the length of every interval is $\frac{1}{N}$, its contribution to the definite integral $\int_{0}^{1}f(z)\ \textrm{d}z$ is $\frac{1}{N}$, and therefore

$$\int_{0}^{1}f(z)\ \textrm{d}z=\frac{MN}{N}=M\ .$$

The integration is possible since the number of discontinuity points of $f$ is at most $2MN$, i.e., a constant for every fixed pair $(N,M)$. In fact, $f$ is constant between every two consecutive discontinuity points, including the boundary points $0$ and $1$ among those. This implies that we can find the total length of intervals where $f$ has the integer value $i$ for $0\leq i\leq MN$, which we denote by $\beta_{i}$. Clearly, $\sum_{i=0}^{MN}\beta_{i}=1$. Imagine sorting the intervals with fixed values of $f$, so that, going from right to left along the $[0,1)$ interval, we have, in this order, a sequence of intervals, the $i+1$-th of which, where $0\leq i\leq MN$, has length $\beta_{i}$ and associated value $i$. This is captured by a non-increasing step function $g$ defined as follows: For every point $z$ where $0\leq z<1$, let $g(z)$ the unique $i$ such that

$$\sum_{j=i+1}^{MN}\beta_{j}\leq z\ \ \mbox{ and \ \ \ }\sum_{j=i}^{MN}\beta_{j}>z\ ;$$

the function $g$ is well-defined, since naturally $\sum_{j=MN+1}^{MN}\beta_{j}=0$. Moreover, it holds that

$$\int_{0}^{1}g(z)\ \textrm{d}z=\sum_{i=0}^{MN}i\beta_{i}=\int_{0}^{1}f(z)\ \textrm{d}z=M\enspace.$$

(1)

We further note that it follows from the definition of $g$ that any (left-closed) interval of length at least $\ell$ contains a point $z$ such that $g(z)\geq f(1-\ell)$, i.e., a point $z$ which is contained in at least $f(1-\ell)$ intervals assigned by the algorithm to the items from the input prefix.

Next, the input may continue in one of many ways. Specifically, consider an eventually fixed $t$ such that $1\leq t\leq\frac{N}{2}-1$. Then, for every $q=t,t+1,\ldots,\frac{N}{2}-1$, there is an input $I_{q}$ which continues after the prefix with $\frac{MN}{q}$ items of length $1-\frac{q}{N}$. Since $q\leq\frac{N}{2}-1$, we have

$$1-\frac{q}{N}\geq 1-\frac{\frac{N}{2}-1}{N}=\frac{1}{2}+\frac{1}{N}>\frac{1}{2}\ .$$

An optimal offline solution assigns all these items the interval $[\frac{q}{N},1]$, and it partitions the $MN$ items of size $\frac{1}{N}$ from the prefix into $q$ subsets of $\frac{MN}{q}$, to be assigned the intervals $[\frac{j-1}{N},\frac{j}{N})$ for $j=1,2,\ldots,q$, i.e., all items from a $j$-th subset are assigned the $j$-th interval. Clearly, the cost of such solution is $\frac{MN}{q}$, i.e.,

$$\text{OPT}(I_{q})=\frac{MN}{q}\enspace.$$

(2)

As for the algorithm, no matter what intervals it assigned to the items of size $1-\frac{q}{N}$, they must all contain the interval $J_{q}=[\frac{q}{N},1-\frac{q}{N})$, whose length is $1-\frac{2q}{N}$. Thus, by aforementioned properties of the function $g$, there is a point $z\in J_{q}$ such that $f(z)\geq g\left(\frac{2q}{N}\right)$, which implies that

$$\text{ALG}(I_{q})\geq g\left(\frac{2q}{N}\right)+\frac{MN}{q}\enspace.$$

(3)

In addition, we consider the prefix of items by itself, i.e., with no further items released, and denote such instance $I_{N/2}$. The optimal offline solution partitions items into $N$ subsets and uses all intervals $[\frac{j-1}{N},\frac{j}{N})$ for $q\leq j\leq N$, so

$$\text{OPT}(I_{N/2})=M\enspace,$$

(4)

while by definition and properties of the function $g$, for the online algorithm we have

$$\text{ALG}(I_{N/2})\geq g\left(0\right)\enspace.$$

(5)

Suppose that the algorithm is asymptotically $R$-competitive. Then, for some additive constant $C$, the following inequality holds for any probability distribution $\{p_{q}\}_{q=t}^{N/2}$ over the instances $\{I_{q}\}_{q=t}^{N/2}$:

$$\mathbb{E}_{q}\left[\text{ALG}(I_{q})\right]\leq R\cdot\mathbb{E}_{q}\left[\text{OPT}(I_{q})\right]+C\enspace.$$

(6)

Plugging in the upper bounds on OPT, i.e., (2) and (4), as well as the lower bounds on ALG, i.e., (3) and (5), we get

$$p_{\frac{N}{2}}\cdot g(0)+\sum_{q=t}^{\frac{N}{2}-1}p_{q}\left(g\left(\frac{2q}{N}\right)+\frac{MN}{q}\right)\leq R\left(p_{\frac{N}{2}}\cdot M+\sum_{q=t}^{\frac{N}{2}-1}p_{q}\frac{MN}{q}\right)+C\enspace,$$

which after moving the terms without $g$ to the right hand side becomes

$$p_{\frac{N}{2}}\cdot g(0)+\sum_{q=t}^{\frac{N}{2}-1}p_{q}\cdot g\left(\frac{2q}{N}\right)\leq R\cdot p_{\frac{N}{2}}\cdot M+\left(R-1\right)\sum_{q=t}^{\frac{N}{2}-1}p_{q}\frac{MN}{q}+C\enspace.$$

Letting $p_{\frac{N}{2}}=\frac{2t}{N}$ and $p_{i}=\frac{2}{N}$ for $t\leq i<N/2$, the left hand side becomes an upper bound on the integral of $g$ over $[0,1)$, so by (1),

$$M=\int_{0}^{1}g(t)\ \textrm{d}t\leq\frac{2t}{N}\cdot g(0)+\frac{2}{N}\sum_{q=t}^{\frac{N}{2}-1}g\left(\frac{2q}{N}\right)\leq\frac{2}{N}\cdot(t\cdot R\cdot M+\sum_{q=t}^{\frac{N}{2}-1}(R-1)\frac{N}{q})+C\enspace.$$

Dividing by $2M$, the term $\frac{C}{2M}$ tends to $0$ for $M\to\infty$, so letting $\tau=\frac{t}{N}$, this inequality becomes

$$\tau\cdot R+(R-1)\sum_{q=\tau\cdot N}^{\frac{N}{2}-1}\frac{1}{q}\geq\frac{1}{2}\enspace.$$

With $N$ growing to infinity, the sum $\sum_{q=\tau\cdot N}^{\frac{N}{2}-1}\frac{1}{q}$ tends to $-\ln(2\tau)$. Rearranging, we have

$$\left(R-1\right)\left(\tau-\ln\left(2\tau\right)\right)\geq\frac{1}{2}-\tau\enspace,$$

where finally letting $\tau\approx 0.212072$ yields the desired lower bound on $R$.

We note that the even though we did not specify the probability distribution over instances upfront, it is fixed, and in particular it does not depend on the deterministic online algorithm, which thus may know the distribution a priori, as stipulated by Yao’s principle.