# Online Simple Knapsack with Reservation Costs

Hans-Joachim Böckenhauer<EMAIL_ADDRESS>Elisabet Burjons<EMAIL_ADDRESS>aachen.de Fabian Frei11footnotemark: 1<EMAIL_ADDRESS>Juraj Hromkovič
<EMAIL_ADDRESS>Henri Lotze<EMAIL_ADDRESS>Peter
Rossmanith<EMAIL_ADDRESS>
###### Abstract

In the _online simple knapsack problem_ we are given a knapsack of unit size
1. Items of size smaller or equal to 1 are presented in an iterative fashion
and an algorithm has to decide for each item whether to reject or permanently
include it into the knapsack without any knowledge about the rest of the
instance. The goal is to pack the knapsack as full as possible. In this work,
we introduce a third option additional to those of packing and rejecting an
item, namely that of reserving an item for the cost of a fixed fraction
$\alpha$ of its size. An algorithm may pay this fraction in order to postpone
its decision on whether to include or reject the item until after the last
item of the instance was presented.

While the classical _online simple knapsack problem_ does not admit any
constantly bounded competitive ratio in the deterministic setting, we find
that adding the possibility of reservation makes the problem constantly
competitive, with varying competitive ratios depending on the value of the
fraction $\alpha$. We give tight bounds for the whole range of reservation
costs, which is split up into four connected areas, depending on the value of
$\alpha$: Up to a value of $0.25$, the competitive ratio is $2$. This is
followed by a competitive ratio of $(1+\sqrt{5-4\alpha})/(2(1-\alpha))$ for
values up to $\sqrt{2}-1$. Afterwards, the competitive ratio is $2+\alpha$ for
values up to $\phi-1$, where $\phi$ is the golden ratio. Finally, the
competitive ratio diverges with a value of $1/(1-\alpha)$ for values between
$\phi-1$ and $1$.

With our analysis, we find a counterintuitive characteristic of the problem:
Intuitively, one would expect that the possibility of rejecting items becomes
more and more helpful for an online algorithm with growing reservation costs.
However, for reservation costs above $\sqrt{2}-1$, an algorithm that is unable
to reject any items tightly matches the lower bound and is thus the best
possible. On the other hand, for any positive reservation cost smaller than
$\sqrt{2}-1$, any algorithm that is unable to reject any items performs
considerably worse than one that is able to reject.

###### keywords:

Online problem, Simple knapsack, Reservation costs

††journal: Journal of Computer and System Sciences

[author2]organization=Department of Computer Science, ETH Zürich,
addressline=Universitätstrasse 6, 8092 Zürich, country=Switzerland

[author1]organization=Department of Computer Science, RWTH Aachen University,
addressline=Ahornstrasse 55, 52074 Aachen, country=Germany

[author3]organization=Department of Computer Science, ETH Zürich,
addressline=Universitätstrasse 6, 8092 Zürich, country=Switzerland

[author4]organization=Department of Computer Science, ETH Zürich,
addressline=Universitätstrasse 6, 8092 Zürich, country=Switzerland

[author5]organization=Department of Computer Science, RWTH Aachen University,
addressline=Ahornstrasse 55, 52074 Aachen, country=Germany

[author6]organization=Department of Computer Science, RWTH Aachen University,
addressline=Ahornstrasse 55, 52074 Aachen, country=Germany

f1f1footnotetext: A preliminary version of parts of this paper has appeared in
the Proceedings of the 38th International Symposium on Theoretical Aspects of
Computer Science (STACS 2021) [3].

##  1 Introduction

Online algorithms can be characterized by receiving their input in an
iterative fashion and having to act in an irrevocable way on each piece of the
input, e. g., by deciding whether to include an element into the solution set
or not. This has to be done with no additional knowledge about the contents or
even the length of the rest of the instance that is still to be revealed. The
goal, as with offline algorithms, is to optimize some objective function. In
order to measure the performance of an online algorithm, it is compared to
that of an optimal offline algorithm on the same instance. The worst-case
ratio between the performances of these algorithms over all instances is then
called the _strict competitive ratio_ of an online algorithm, as introduced by
Sleator and Tarjan [22].

One of the arguably most basic and famous problems of online computation is
called the _ski rental problem_ [19]. In this problem, someone is going on a
skiing holiday of not yet fixed duration without owning the necessary
equipment. On each day, she decides, based solely on that day’s short-term
weather report, whether skiing is possible on that day or not. On each day
with suitable weather, she can either buy the equipment or rent it for that
day

for a fixed percentage of the cost of buying. Arguably, the only interesting
instances are those in which a selected number of days are suitable for
skiing, followed by the rest of the days at which she is unable to go skiing
anymore. This is simply due to the fact that, as long as she has not decided
to buy a pair of ski yet, a day at which no skiing is possible requires no
buy-or-rent decision. Thus, the problem can be simplified as follows: The
input is a string of some markers that represent days suitable for skiing, and
as soon as the instance ends, skiing is no longer possible.

This notion of delaying a decision for a fixed percentage of the cost is the
model that we want to study in this work. Note that, while the ski-rental
problem in its above-mentioned form only models a single buy-or-rent decision
(buying or renting a single commodity), iterated versions of it have been
discussed in the literature, with important applications, e. g., to energy-
efficient computing [15, 1, 4]. In this paper, we investigate the power of
delaying decisions for another more involved problem, namely the online
knapsack problem.

The _knapsack problem_ is defined as follows. Given a set of items $I$, a size
function $w\colon I\to\mathbf{R}$ and a gain function $g\colon
I\to\mathbf{R}$, find a subset $S\subseteq I$ such that the sum of sizes of
$S$ is less or equal to the so-called _knapsack capacity_ (which we assume to
be normalized to $1$ in this paper) and the sum of the gains is maximized. The
online variant of this problem reveals the items of $I$ piece by piece, with
an algorithm having to immediately decide whether to pack a revealed item or
to discard it.

The knapsack problem is a classical hard optimization problem, with the
decision variant being shown to be NP-complete as one of Karp’s 21 NP-complete
problems [18]. The offline variant of this problem was studied extensively in
the past, showing for example that it admits a fully polynomial time
approximation scheme [14].

A variant of this problem in which the gains of all items coincide with their
respective sizes is called the _simple knapsack problem_ ; it is also NP-
complete. Both variants do not admit a constantly bounded competitive ratio
[20]. In this paper, we focus on the online version of the latter variant,
which we simply refer to as the _online knapsack problem_ , for short
OnlineKP, if not explicitly stated otherwise.

We propose a rather natural generalization of the online knapsack problem.
Classically, whenever an item of the instance is presented, an online
algorithm has to irrevocably decide whether to include it into its solution
(i. e., pack it into the knapsack) or to discard it. In our model, the
algorithm is given a third option, which is to reserve an item for the cost of
a fixed percentage $0\leq\alpha\leq 1$ of its value. The algorithm may reserve
an arbitrary number of items of the instance and decide to pack or discard
them at any later point. Philosophically speaking, the algorithm may pay a
prize in order to (partially) “go offline.” It is easy to see that, for
$\alpha=0$, the complete instance can be learned before making a decision
without any disadvantages, essentially making the problem an offline problem,
while, for $\alpha=1$, reserving an item is not better than discarding it
because packing a reserved item does not add anything to the gain.

This extension to the knapsack problem is arguably quite natural: Consider
somebody trying to book a flight with several intermediate stops. Since flight
prices are subject to quick price changes, it might be necessary to invest
some reservation costs even for some flights not ending up in the final
journey. The knapsack problem with reservations might also be seen as a simple
model for investing in a volatile stock market, where a specific type of
derivates is available (at some cost) that allows the investor to fix the
price of some stock for a limited period of time.

One of the key properties of our reservation model applied to the simple
knapsack problem is its unintuitive behavior with respect to rejecting items.
It shows sharp thresholds for the competitive ratio at seemingly arbitrary
points: For some interval of low reservation charges, the competitive ratio is
not affected by the charge at all, on the next interval, it follows a
nonlinear function, penultimately it depends linearly on the charge, and on
the last interval, the competitive ratio grows even faster. This behavior is
further discussed in the following subsection.

The OnlineKP has been extensively studied under many other variations,
including buffers of constant size in which items may be stored before
deciding whether to pack them, studied by Han et al. [12]. Here, the authors
allow for a buffer of size at least the knapsack capacity into which the items
that are presented may or may not be packed and from which a subset is then
packed into the actual knapsack in the last step. They extensively study the
case in which items may be irrevocably removed from the buffer. Our model can
be understood as having an optional buffer of infinite size, with the caveat
that each buffered item induces a cost. A variant without an additional
buffer, but with the option to remove items from the knapsack at a later point
was studied by Iwama et al. [16]. The same model with costs for each removal
that are proportional to a fraction $f$ of each item from the knapsack was
researched by Han et al. [11], which is closer to our model. Their model
allows an algorithm to remove items that were already packed into the
knapsack, for a proportion of the value of these items. However, we do not
know of any simple reduction from one model to the other, which is supported
by the considerably different behavior of the competitive ratio relative to
the reservation cost. For OnlineKP, Han et al. show that the problem is
2-competitive for a removal cost factor $f\leq 0.5$ and becomes
$(1+f+\sqrt{f^{2}+2f+5})/2$-competitive for $f>0.5$.

Other models of the online (simple) knapsack problem have been studied as
well, such as the behavior of the resource-augmentation model, where the
knapsack of the online algorithm is slightly larger than the one of the
offline algorithm on the same instances, studied by Iwama et al. [17]. When
randomization is allowed, the OnlineKP becomes 2-competitive using only a
single random bit and does not increase its competitive ratio with any
additional bits of randomization [6]. A relatively young measure of the
informational complexity of a problem is that of advice complexity, introduced
by Dobrev, Královič, and Pardubská [9], revised by Hromkovič et al. [13] and
refined by Böckenhauer et al. [5]. In the standard model, an online algorithm
is given an advice tape of bits that an oracle may use to convey some bits of
information to an online algorithm about the instance in order to improve its
performance. Not surprisingly, a single advice bit also improves the
competitive ratio to 2, but interestingly, any advice in the size of $o(\log
n)$ advice bits does not improve this ratio [6].

###  1.1 Our Contributions

We study the behavior of the knapsack problem with reservation costs for a
reservation factor $0<\alpha<1$. We analyze four subintervals for $\alpha$
separately with borders at $1/4$, $\sqrt{2}-1$ and $\phi-1\approx 0.618$,
where $\phi$ is the golden ratio. The bounds that we are providing, which are
illustrated in Figure 1, can be found in Table 1. We prove matching upper and
lower bounds for each interval.

Table 1: Competitive ratios proven in this work. $\alpha$ | Competitive ratio | Lower bound | Upper bound
---|---|---|---
$0\;<\;$ | $\alpha\;\leq\;0.25$ | $2$ | Thm. 12 | Thm. 1
$0.25\;<\;$ | $\alpha\;\leq\;\sqrt{2}-1$ | $\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ | Thm. 13 | Thm. 1
$\sqrt{2}-1\;<\;$ | $\alpha\;<\;\phi-1$ | $2+\alpha$ | Thm. 13 | Thm. 2, 3
$\phi-1\;\leq\;$ | $\alpha\;<\;1$ | $\frac{1}{1-\alpha}$ | Thm. 13 | Thm. 11
$0$$0.2$$0.4$$0.6$$0.8$$1$$2$$3$$4$$5$$\alpha$Competitive Ratio Figure 1: A
schematic plot of the relation between reservation costs and the resulting
competitive ratio, which is proven in this work.

We also take a look at a subclass of algorithms for this problem that never
discard presented items up to a point where they stop processing the rest of
the input, with arguably paradoxical results: One would expect that, for very
small reservation costs, reserving items instead of rejecting them right away
is more helpful than doing the same with large reservation costs and that
rejecting becomes more and more helpful with increasing reservation costs. But
we prove that, while, for small values of $\alpha$, every algorithm that is
unable to reject items is strictly dominated by algorithms that are able to
reject items, for larger values of $\alpha$ this is not the case, with our
algorithms used for $\alpha\geq\sqrt{2}-1$ being nonrejecting and matching
their lower bounds.

We cannot give a definitive answer on why this behavior can be observed. Our
intuition is that, for higher reservation costs, the behavior is more similar
to the model without reservations. In this classical model, any errors that
occur by ultimately not packing an item are punished severely, so while
reserving everything is costly, it is not worse than rejecting any items.

The remainder of this paper is structured as follows: In Section 2, we present
the upper bounds for all intervals. We divide this section by first presenting
a more general algorithm that provides us with the wanted upper bounds for
values of $\alpha$ up to $\sqrt{2}-1$ and continue with much simpler
algorithms for values of $\alpha$ larger than $\sqrt{2}-1$. In Section 3, we
look at matching lower bounds, with a specialized lower bound for values of
$\alpha$ smaller than $0.25$ and a uniform approach for all higher values.
Section 4 is devoted to a discussion of algorithms that are unable to reject
items. We conclude the paper in Section 5.

###  1.2 Preliminaries

Our model can be defined as follows. Consider a knapsack of size 1 and a
_reservation factor_ $\alpha$, with $0\leq\alpha\leq 1$. A _request sequence_
$I$ is a list of item sizes $x_{1},x_{2},\ldots,x_{n}$ with $x_{i}\leq 1$ for
$1\leq i\leq n$, which arrive sequentially. At time step $i$, the knapsack is
filled up to some size $t_{i}\leq 1$ and the reserved items add up to size
$r_{i}$. When an item with size $x_{i}$ arrives, an online algorithm may
_pack_ this item into the knapsack if $x_{i}+t_{i}\leq 1$, it may also
_reject_ the item, or _reserve_ the item at cost $\alpha\cdot x_{i}$.

At step $n+1$, no new items arrive and the knapsack contains all items that
were taken with total size $t_{n}$ and the reserved items have size $r_{n}=R$.
An algorithm can additionally pack any of the reserved items which still fit
into the knapsack, up to some size $t\leq 1$. The _gain_ of an algorithm
${\mathtt{A}}$ solving ReserveKP with a reservation factor $\alpha$ on an
instance $I$ is $\text{gain}_{{\mathtt{A}}}(I)=t-\alpha\cdot R$.

The _strict competitive ratio_ of an algorithm ${\mathtt{A}}$ on an instance
$I$ is, given a solution with optimal gain $\text{gain}_{{\mathtt{OPT}}}(I)$
on this instance,
${\rho}_{{\mathtt{A}}}(I)={\text{gain}_{{\mathtt{OPT}}}(I)}/{\text{gain}_{{\mathtt{A}}}(I)}$.
The general strict competitive ratio of an algorithm ${\mathtt{A}}$ is taken
as the worst case over all possible instances,
${\rho}_{{\mathtt{A}}}=\max_{I}\\{{\rho}_{{\mathtt{A}}}(I)\\}$.

The strict competitive ratio as defined above is a special case of the well-
known _competitive ratio_ which relaxes the above definition by allowing for a
constant additive term in the definition. Note that this generalized
definition only makes sense for online problems in which the optimal solution
has unbounded gain. Since the gain of an optimal solution for ReserveKP is
bounded by the knapsack capacity, we only work with strict competitive ratios
in this paper and will simply call it _competitive ratio_ from now on. For a
thorough introduction to competitive analysis of online algorithms, see the
textbooks by Borodin and El-Yaniv [7] and by Komm [19].

##  2 Upper Bounds

We start by presenting an algorithm that gives us bounds for smaller values of
$\alpha$. While the algorithm that is presented in the following subsection
does not diverge from the lower bounds for values of $\alpha$ bigger than
$\sqrt{2}-1$, we handle the two function segments above this threshold
seperately, using much simpler algorithms. This is done to show a curious
observation that is further discussed in section 4. This observation states
that an algorithm that tightly matches the lower bound for these segments no
longer has to reject any items in order to be optimal.

###  2.1 Upper Bound for $0<\alpha<\sqrt{2}-1$

We present Algorithm 1 and first look at the competitive ratio after each of
the stop statements is reached. The interesting part of the analysis is then
done in Theorem 1, which deals with the case that none of the stop statements
are reached during the run of the algorithm.

We define $\mu=1/(\rho(1-\alpha))$, where we will choose $\rho$ as our claimed
competitive ratio, depending on the area of values for $\alpha$ that we want
to analyze. We keep track of the reserved items in the set $R_{s}$. We denote
the largest packing of a set $I$ of items that is of size at most 1 by $POPT$.

The algorithm is split up into several parts, while a reservation is only made
in line 4 and if one criterion is met: If the gain from the current item plus
the gain of everything reserved so far is still below our wanted gain, we
reserve the item. This especially means that the current item and the gain
from our reserve itself are both smaller than $1/\rho$ if this condition
triggers.

If we do not reserve, we know that the new item together with the gain of our
reserve exceeds our wanted gain. It could however be the case that this sum
also exceeds 1 and thus does not constitute a valid packing. Thus, we pack in
line 5 if the sum is smaller than 1 and are done or we continue otherwise.

We also know that $R(1-\alpha)<1/\rho$, and thus $R<1/(\rho(1-\alpha))=\mu$
always holds, as we do not reserve items that would cause a violation of this
condition. This, together with the knowledge that $x_{k}$ is too big to pack
it together with $R$ lets us derive that $x_{k}>1-\mu$. Thus, if all other
items from $R_{s}$ are smaller than $1-\mu$, we can simply remove them
iteratively from our knapsack until $x_{k}+R\leq 1$ holds. This leads to our
wanted result in line 6, as we know that the reservation costs up to this
point are at most $\mu\alpha$ (since $R<\mu$), our final packing is of size at
least $\mu$ and thus our gain is $\mu-\mu\alpha=1/\rho$.

This leaves us with a corner case in which the previous conditions hold,
except that there is at least one other item in $R_{s}$ which is bigger than
$1-\mu$. We then simply calculate in line 7 if we are able to achieve our
wanted competitive ratio using the new item $x_{k}$ anyway and reject the item
in line 8 otherwise.

Thus, we are only left to analyze the competitive ratio of the algorithm in
the case that none of the _stop_ statements triggered at the end of the
instance, which we do in the following theorem.

1:$R:=0$;

2:$R_{s}:=\emptyset$;

3:for $k=1,\ldots,n$ do

4: if $x_{k}+R(1-\alpha)<1/\rho$ then $R:=R+x_{k}$,
$R_{s}:=R_{s}\cup\\{x_{k}\\}$

5: else if $x_{k}+R\leq 1$ then pack optimally and stop

6: else if $\forall j\in R_{s}:x_{j}\leq 1-\mu$ then pack optimally and stop

7: else if $POPT(x_{k}\cup R_{s})-R\alpha\geq 1/\rho$ then pack optimally and
stop

8: else reject $x_{k}$

9:pack the reserved items optimally

Algorithm 1 Competitive ratio of $2$ for $\alpha\leq 0.25$ and of
$\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ for $\alpha\leq\sqrt{2}-1$

######  Theorem 1.

There is an algorithm for ReserveKP with a competitive ratio of
$\max\\{\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)},2\\}$ if $0<\alpha<\sqrt{2}-1$.

###### Proof.

In order to show this property, we analyze Algorithm 1 and show that it
provides us with the wanted upper bound. We already saw in the description of
the algorithm that in all of the _stop_ statements, the claim of the theorem
holds if we set $\rho$ to our wanted competitive ratios. We are thus left with
analyzing the performance of the algorithm in the case that none of the _stop_
statements are reached during its run.

We first argue that, whenever a new item $x_{k}$ is rejected, the reserve
contains exactly one item $x_{i}$ of size at least $1-\mu$. We already know
that for $x_{k}$ to be rejected, the _stop_ condition in line 6 did not
trigger, which tells us that, in line 8, there is at least one item bigger
than $1-\mu$ in our reserve already. We now look at the time where the first
item of size at least $1-\mu$ has already been reserved and assume that
$x_{k}$ is of size at least $1-\mu$ as well. Then we do not reserve this item
since

$\displaystyle x_{k}+R(1-\alpha)$ $\displaystyle\geq(1-\mu)+(1-\mu)(1-\alpha)$
$\displaystyle=\biggl{(}1-\frac{1}{\rho(1-\alpha)}\biggr{)}(2-\alpha)$
$\displaystyle\geq 1/\rho$

where the last inequality holds for $\rho=2$ and all $\alpha\leq
1-1/\sqrt{2}\approx 0.293$, in particular for $\alpha\leq 0.25$. The
inequality remains true for $\rho=\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ and
any $0<\alpha<1$, thus in particular for the interval considered in the
theorem statement.

Next, we argue that any item that is rejected is of size larger than $1/2$.
This can be easily verified using the fact that the _stop_ statement in line 5
did not trigger, and thus $x_{k}>1-R$ holds. Since we additionally know that
$R$ contains at least one item of size at least $1-\mu$, it has to hold that
$x_{k}>\mu$, which is bigger than $1/2$ for $0<\alpha<\sqrt{2}-1$.

This also means that any optimal solution can contain at most one of the items
that the algorithm discards. Thus, we can ignore any items of an instance that
both our algorithm and an optimal algorithm discard and fix one item of size
larger than $1/2$ (there can only be one in any valid solution) as the unique
item that is part of the optimal solution, but discarded by our algorithm.

Let now $x_{i}$ be the unique item that the algorithm rejects, but that is
part of the optimal solution and let $x_{j}$ be the largest reserved item of
the algorithm at the time that $x_{i}$ is rejected. As we discard $x_{i}$, we
know by the conditionals that we passed and that were not triggered that both
$x_{i}\leq POPT(x_{k}\cup R_{s})\leq 1/\rho+R\alpha$ and $x_{i}+x_{j}>1$ have
to hold. We also know that the only rejected item from the optimal solution is
$x_{i}$ and that every other item of this solution was reserved by our
algorithm.

Let $b$ be the total size of all items reserved by our algorithm before
$x_{j}$ arrived. On the other hand, let $a$ be the total size of all items
reserved by our algorithm after item $x_{i}$ is rejected. At the moment that
$x_{i}$ is rejected, we know by line 7 that $x_{i}\leq POPT(x_{k}\cup
R_{s})\leq 1/\rho+(x_{j}+b)\alpha$. We use this term between steps (1) and (2)
of the following calculation. Together with $x_{i}+x_{j}>1$, we can derive
$1-x_{j}<x_{i}\leq 1/\rho+(x_{j}+b)\alpha$ which solved for $x_{j}$ yields
$\frac{1-1/\rho-b\alpha}{1+\alpha}\leq x_{j}$. This is used between steps (6)
and (7) of the following inequation chain. We can now derive the following. To
summarize, the optimal algorithm has a gain of $x_{i}+b+a$. Algorithm 1 also
has a gain of $a+b$, but packs $x_{j}$ instead of $x_{i}$ and has to pay
reservation costs of $\alpha$ for $a$, $b$ and $x_{i}$. Hence, we have

$\displaystyle\frac{gain_{\mathtt{OPT}}}{gain_{\mathtt{A}}}$
$\displaystyle\leq\frac{x_{i}+b+a}{(1-\alpha)(x_{j}+b+a)}$ Use: $x_{i}\leq
1/\rho+(x_{j}+b)\alpha$ (1)
$\displaystyle\leq\frac{1}{1-\alpha}\cdot\frac{1/\rho+(x_{j}+b)\alpha+b+a}{x_{j}+b+a}$
Add $a\cdot\alpha$ to numerator (2)
$\displaystyle\leq\frac{1}{1-\alpha}\cdot\frac{1/\rho+x_{j}\alpha+(b+a)(1+\alpha)}{x_{j}+b+a}$
Take $1+\alpha$ as common factor (3)
$\displaystyle=\frac{1+\alpha}{1-\alpha}\cdot\frac{\frac{1}{\rho(1+\alpha)}+x_{j}\frac{\alpha}{1+\alpha}+b+a}{x_{j}+b+a}.$
(4)

If the fraction to the right of $\frac{1+\alpha}{1-\alpha}$ is at most 1, we
are done: It holds that $\frac{1+\alpha}{1-\alpha}\leq 2$ for $\alpha\leq 1/3$
and also $\frac{1+\alpha}{1-\alpha}\leq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$
for $\alpha\leq\sqrt{2}-1$. Otherwise, we use that removing the term $a+b$
from both the numerator and the denominator can only increase the value of the
right fraction and continue as follows.

$\displaystyle\frac{gain_{\mathtt{OPT}}}{gain_{\mathtt{A}}}$
$\displaystyle\leq\frac{1+\alpha}{1-\alpha}\cdot\frac{\frac{1}{\rho(1+\alpha)}+x_{j}\frac{\alpha}{1+\alpha}}{x_{j}}$
Simplify equation (5) $\displaystyle=\frac{\frac{1}{\rho
x_{j}}+\alpha}{1-\alpha}$ Use $x_{j}\geq\frac{1-1/\rho+b\alpha}{1+\alpha}$ (6)
$\displaystyle\leq\frac{\frac{1+\alpha}{\rho-1+\rho
b\alpha}+\alpha}{1-\alpha}$ Remove $\rho b\alpha$ (7)
$\displaystyle\leq\frac{\frac{1+\alpha}{\rho-1}+\alpha}{1-\alpha}$ Replace
$\rho$ by 2 ($\rho\geq 2$) (8) $\displaystyle\leq\frac{1+2\alpha}{1-\alpha}$
(9)

This gives us our wanted competitive ratio of at most $\rho=2$ for $\alpha\leq
0.25$ and likewise of $\rho=\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ for
$0.25\leq\alpha\leq\sqrt{2}-1$. ∎

###  2.2 Upper Bound for $\frac{1}{6}<\alpha<\phi-1$

We now prove a general upper bound for $\alpha<\phi-1$. We split the proof,
into two pieces: Theorem 2 handles the case for values of $\alpha$ up to
$\frac{1}{2}$, . Theorem 3 contains an induction over the number of large
elements in an instance, which proves the upper bound for the rest of the
interval up to $\phi-1$.

######  Theorem 2.

There exists an algorithm for ReserveKP with a competitive ratio of at most
$2+\alpha$ if $0<\alpha\leq\frac{1}{2}$.

######  Theorem 3.

There exists an algorithm for ReserveKP with a competitive ratio of at most
$2+\alpha$ if $\frac{1}{2}<\alpha<\phi-1$.

$R:=0$;

for $k=1,\ldots,n$ do

if $x_{k}+(1-\alpha)R\geq 1/(2+\alpha)$ then

pack $x_{1},\ldots,x_{k}$ optimally;

stop

else

reserve $x_{k}$;

$R:=R+x_{k}$

pack $x_{1},\ldots,x_{n}$ optimally

Algorithm 2 Competitive ratio of $2+\alpha$ for $0<\alpha\leq\phi-1$

We consider Algorithm 2, which, unlike Algorithm 1, does not reject any
offered item until it reaches the desired gain and stops processing the rest
of the input. In Section 4, we further discuss this class of algorithms and
when they are optimal. We need the following technical lemmas.

######  Lemma 4.

The size of $R$ in Algorithm 2 is never larger than
$1/{(2+\alpha)(1-\alpha)}$.

###### Proof.

Let us consider a request sequence $x_{1},\ldots,x_{n}$ for Algorithm 2, such
that $x_{k}$ triggers the packing, i. e., $x_{k}+(1-\alpha)R\geq
1/(2+\alpha)$.

We know that $x_{k-1}+(1-\alpha)R^{\prime}<\frac{1}{2+\alpha},$ where $R$ is
defined as $R=x_{k-1}+R^{\prime}$. But $x_{k-1}\geq(1-\alpha)x_{k-1}$ which
means that $(1-\alpha)R=(1-\alpha)x_{k-1}+(1-\alpha)R^{\prime}\leq
x_{k-1}+(1-\alpha)R^{\prime}<\frac{1}{2+\alpha}.$ Thus,
$R<\frac{1}{(2+\alpha)(1-\alpha)}.$

Observe that this is, by construction, the largest possible value that $R$ can
take before the algorithm triggers the packing, thus, we have proved the
claim. ∎

Note that, for every considered value of $\alpha$, the upper bound on $R$ is
positive, that is, $(2+\alpha)(1-\alpha)>0$ if $\alpha$ is smaller than 1\.
With Lemma 4, we can prove the following claim.

######  Lemma 5.

If Algorithm 2 packs at least $1/{(2+\alpha)(1-\alpha)}$ into the knapsack,
then its competitive ratio is at most $2+\alpha$.

###### Proof.

We know that, if the algorithm packs at least
$\frac{1}{(2+\alpha)(1-\alpha)}$, the gain of the algorithm,
$\rm{gain}_{{\mathtt{A}}}$, is at least $\frac{1}{(2+\alpha)(1-\alpha)}-\alpha
R.$ But, by Lemma 4, $R<1/(2+\alpha)(1-\alpha)$, which means that
$\rm{gain}_{{\mathtt{A}}}(I)\geq\frac{1}{(2+\alpha)(1-\alpha)}-\frac{\alpha}{(2+\alpha)(1-\alpha)}=\frac{1}{2+\alpha},$
providing us with the desired upper bound on the competitive ratio. ∎

The next lemma allows us to restrict our attention to ordered sequences of
items. It proves that, if an instance violates the upper bound for Algorithm
2, we can rearrange the first $k-1$ items in decreasing order and get another
hard instance.

######  Lemma 6.

If $x_{1},\ldots,x_{n}$ is an instance for Algorithm 2, whose packing is
triggered by $x_{k}$, with a competitive ratio larger than $2+\alpha$, then
there is another instance
$x_{i_{1}},x_{i_{2}},x_{i_{3}},\ldots,x_{i_{k-1}},\allowbreak
x_{k},\ldots,x_{n}$ where $(i_{1},i_{2},\ldots,i_{k-1})$ is a permutation of
$(1,\ldots,k-1)$ and $x_{i_{1}}\geq x_{i_{2}}\geq\ldots\geq x_{i_{k-1}}$, that
also has a competitive ratio larger than $2+\alpha$.

###### Proof.

We show how to transform the original sequence such that the number of
inversions is reduced by one. Repeating this transformation yields the desired
result.

Let $x_{1},\ldots,x_{n}$ be an instance for Algorithm 2, such that packing is
triggered by $x_{k}$ with a competitive ratio larger than $2+\alpha$. Assume
that $x_{i}<x_{i+1}$ for some $i<k-1$. We prove that we will get again an
instance with a competitive ratio larger than $2+\alpha$ if we swap the
positions of $x_{i}$ and $x_{i+1}$. It is easy to see that this transformation
preserves the sum of the first $k-1$ items. To show that it is a sequence that
does not trigger the packing after the $i$th or $(i+1)$st item, we have to
verify that

$x_{i+1}<\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+\cdots+x_{i-1})$ (10)

and

$x_{i}<\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+\cdots+x_{i-1}+x_{i+1})\;.$ (11)

Here, (10) is straightforward, since $x_{k}$ for $k>i+1$ triggering the
packing in the unmodified instance implies
$x_{i+1}<\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+\cdots+x_{i})$. We prove (11) by
means of a contradiction. Assume, that

$x_{i}\geq\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+\cdots+x_{i-1}+x_{i+1})\;.$ (12)

We also know that, for $1\leq j\leq i+1$,

$x_{j}\leq\frac{1}{2+\alpha}-(1-\alpha)(x_{1}-\ldots-x_{j-1})\;,$ (13)

and by construction

$x_{i}<x_{i+1}\;.$ (14)

If we define $z=\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+\cdots+x_{i-1})$, then we
can rewrite (12), (13) for $j=i+1$, and (14) as

$\displaystyle x_{i}$ $\displaystyle\geq z-\textstyle(1-\alpha)x_{i+1}$
$\displaystyle x_{i+1}$ $\displaystyle\leq z-\textstyle(1-\alpha)x_{i}$
$\displaystyle x_{i}$ $\displaystyle<x_{i+1}\;.$

If we modify the first two equations to isolate the term $(1-\alpha)^{-1}z$,
we obtain

$\displaystyle\frac{x_{i}}{(1-\alpha)}+x_{i+1}$
$\displaystyle\geq\frac{z}{(1-\alpha)}$
$\displaystyle\frac{x_{i+1}}{(1-\alpha)}+x_{i}$
$\displaystyle\leq\frac{z}{(1-\alpha)}\;,$

which means that

$\frac{x_{i+1}}{(1-\alpha)}+x_{i}\leq\frac{x_{i}}{(1-\alpha)}+x_{i+1}\;,$

that is, these two equations are satisfiable if and only if $x_{i+1}\leq
x_{i}$.

It remains to show that the new sequence has a competitive ratio larger than
$2+\alpha$. Although the order of $x_{1},\ldots,x_{k-1}$ has been changed, the
requests are still the same and all of them are reserved and trigger a packing
in $x_{k}$ with the same reservation size, just as before the transformation.
Hence, if there was no way to pack the items well enough before the
transformation, it also cannot be done afterwards. ∎

From Lemma 5, we know that, if Algorithm 2 packs at least
$1/(2+\alpha)(1-\alpha)$, this guarantees a competitive ratio of at most
$2+\alpha$. Thus, if we have enough elements that are smaller than the gap of
size $1-1/(2+\alpha)(1-\alpha)$, those elements can be packed greedily and
always achieve the desired competitive ratio. Let us call _small items_ those
of size smaller than

$1-\frac{1}{(2+\alpha)(1-\alpha)}=\frac{(2+\alpha)(1-\alpha)-1}{(2+\alpha)(1-\alpha)}=\frac{1-\alpha-\alpha^{2}}{(2+\alpha)(1-\alpha)}\;$
(15)

This definition is only valid when (15) is positive, that is, when
$1-\alpha-\alpha^{2}\geq 0$, which is the case if $0<\alpha\leq\phi-1$,
including our desired range. We call _large items_ those of larger size. Let
$\alpha_{4}$ be the unique positive real root of the polynomial
$1-2\alpha-\alpha^{2}+\alpha^{3}$, i. e.,

$\alpha_{4}=\frac{1}{3}+\frac{2\sqrt{7}}{3}\cos{\biggl{(}\frac{1}{3}\arccos{\biggl{(}-\frac{1}{2\sqrt{7}}\biggr{)}}-\frac{2\pi}{3}\biggr{)}}\approx
0.445\;.$

######  Lemma 7.

Given any request sequence $x_{1}\geq x_{2}\geq\ldots\geq
x_{k-1},x_{k},\ldots,x_{n}$, where $x_{k}$ triggers the packing in Algorithm
2, there is at most one large item if $0<\alpha\leq\alpha_{4}$ and there are
at most two large items if $\alpha_{4}<\alpha\leq 0.5$.

###### Proof.

Assume by contradiction that there exists a request sequence where $x_{1}\geq
x_{2}\geq\ldots\geq
x_{i}\geq\frac{1-\alpha-\alpha^{2}}{(2+\alpha)(1-\alpha)}$, with $k>i$. Any
item $x_{j}$ with $j\leq i$ satisfies

$x_{j}\leq\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+x_{2}+\ldots+x_{j-1})\;,$

in particular,

$x_{i}\leq\frac{1}{2+\alpha}-(1-\alpha)(x_{1}+x_{2}+\ldots+x_{i-1})\;.$ (16)

All of the contributions of previous requests are negative, so in order to
obtain a maximal value for $x_{i}$, we need that $x_{1},\ldots,x_{i-1}$ are
minimal, but by construction, still greater or equal than $x_{i}$. Thus, the
maximal value is obtained when $x_{1}=x_{2}=\ldots=x_{i}$. In this case, we
obtain from (16) the upper bound
$x_{i}\leq\frac{1}{2+\alpha}-(1-\alpha)(i-1)x_{i}$ which we solve for $x_{i}$
and obtain $x_{i}\leq\frac{1}{(2+\alpha)(i(1-\alpha)+\alpha)}$.

We also know that $x_{i}$ is a large item, thus we can also state
$x_{i}\geq\frac{1-\alpha-\alpha^{2}}{(2+\alpha)(1-\alpha)}$ as a lower bound
for $x_{i}$.

Thus we get
$\frac{1}{(2+\alpha)(i(1-\alpha)+\alpha)}\geq\frac{1-\alpha-\alpha^{2}}{(2+\alpha)(1-\alpha)}$
which we solve for $i$ to obtain $i\leq
1+\frac{\alpha^{2}}{(1-\alpha)(1-\alpha-\alpha^{2})}$. In particular, for
$i=2$ we get
$2(1-\alpha)(1-\alpha-\alpha^{2})\leq(1-\alpha)(1-\alpha-\alpha^{2})+\alpha^{2}$
which is equivalent to $(1-\alpha)(1-\alpha-\alpha^{2})\leq\alpha^{2}$ and
thus to $1-2\alpha-\alpha^{2}+\alpha^{3}\leq 0$, which means that the number
of large items is strictly smaller than $2$ for $\alpha\leq\alpha_{4}$.

For $i=3$, we get
$3(1-\alpha)(1-\alpha-\alpha^{2})\leq(1-\alpha)(1-\alpha-\alpha^{2})+\alpha^{2}$
or equivalently $2(1-2\alpha+\alpha^{3})\leq\alpha^{2}$. Hence,
$2-4\alpha-\alpha^{2}+2\alpha^{3}\leq 0$, which means that the number of large
items is strictly smaller than 3 for $\alpha\leq 0.5$, since $0.5$ is the
unique positive real root of the left-hand-side polynomial. ∎

Now we are ready to prove the claimed competitive ratio of Algorithm 2.

###### Proof of Theorem 2.

Let us consider first the case where $\alpha\leq\alpha_{4}$, which means that
only one large element can appear in the request sequence without triggering
the packing. We know that, if $x_{1}\geq 1/(2+\alpha)$, then the algorithm
will take it and our competitive ratio will be at most $2+\alpha$, and if a
request sequence ends without triggering the packing, then the optimum would
be $x_{1}+\ldots+x_{n}=s<1$ and Algorithm 2 would have a gain of
$(1-\alpha)s$, so the competitive ratio will be at most
$1/(1-\alpha)<2+\alpha$.

Otherwise, assume that there is a shortest sequence containing at least two
elements, which at some point, namely with request $x_{k}$, triggers Algorithm
2 to pack. We now consider all possible cases.

If $x_{1}+\ldots+x_{k}\leq 1$, then we know that the gain of the algorithm is
$x_{k}+(1-\alpha)(x_{1}+\ldots+x_{k-1})$, which is larger than $1/(2+\alpha)$
by construction.

We are now in the case where $x_{1}+\ldots+x_{k}>1$. If all of the elements of
the request sequence are small, Algorithm 2 packs $x_{k}$ and then it can
greedily pack elements from $x_{1},\ldots,x_{k-1}$. Because these elements all
have size smaller than $1-\frac{1}{(2+\alpha)(1-\alpha)}$, we know that
Algorithm 2 will be able to pack at least $\frac{1}{(2+\alpha)(1-\alpha)}$
into the knapsack, obtaining a competitive ratio of at most $2+\alpha$ by
Lemma 5.

If not all elements are small, we know that at most $x_{1}$ is a large
element, and we do a further case distinction. If $x_{1}+x_{k}<1$, then we
pack them, and we greedily pack the rest of the items, obtaining a competitive
ratio of at most $2+\alpha$ with the same argument as in the previous case. If
$x_{1}+x_{k}>1$, then we consider two cases. If
$x_{2}+\ldots+x_{k}>\frac{1}{(2+\alpha)(1-\alpha)}$, we can again greedily
pack the small items until we obtain the desired competitive ratio. Otherwise,
we know that $x_{k}>1-x_{1}$ and
$x_{2}+\ldots+x_{k}<\frac{1}{(2+\alpha)(1-\alpha)}$ and thus
$x_{2},\ldots,x_{k}$ can all be packed into the knapsack. In this case, we can
calculate the gain of Algorithm 2 as

$\displaystyle x_{2}+\ldots+x_{k}-\alpha(x_{1}+\ldots+x_{k-1})$
$\displaystyle=x_{k}+(1-\alpha)(x_{2}+\ldots+x_{k-1})-\alpha x_{1}$
$\displaystyle>1-x_{1}-\alpha x_{1}+(1-\alpha)(x_{2}+\ldots+x_{k-1})$
$\displaystyle=1-(1+\alpha)x_{1}+(1-\alpha)(x_{2}+\ldots+x_{k-1})$
$\displaystyle>1-\frac{(1+\alpha)}{(2+\alpha)}+(1-\alpha)(x_{2}+\ldots+x_{k-1})$
$\displaystyle=\frac{1}{(2+\alpha)}+(1-\alpha)(x_{2}+\ldots+x_{k-1})\;,$

where we used the fact that $x_{k}>1-x_{1}$, and that $x_{1}<1/(2+\alpha)$
since it did not trigger the packing. This gain is larger than $1/(2+\alpha)$
and we obtain the desired bound for the competitive ratio.

Now, let us consider the case where $\alpha\leq 0.5$, which means that the
request sequence either has at most two large elements or it is shorter than 3
elements. If we get a request sequence of $2$ elements, the first one has to
be $x_{1}<1/(2+\alpha)$, otherwise we already have the desired competitive
ratio by taking that element. Now, if $x_{2}\leq 1-1/(2+\alpha)$, then both
elements fit into the knapsack and we get again a competitive ratio of at most
$1/(1-\alpha)<2+\alpha$. Otherwise, $x_{2}>1-1/(2+\alpha)$, so the algorithm
can pack $x_{2}$ and obtain a gain of at least
$1-1/(2+\alpha)-\alpha/(2+\alpha)=1/(2+\alpha)$.

If the request sequence has at least length 3, we do a further case
distinction. As in the previous case, if a request sequence ends without
triggering the packing, then the optimal packing is $x_{1}+\ldots+x_{n}=s<1$
and Algorithm 2 has a gain of $(1-\alpha)s$, so the competitive ratio is at
most $1/(1-\alpha)<2+\alpha$. Otherwise, assume that there is a shortest
contradictory sequence which at some point $x_{k}$ triggers Algorithm 2 to
pack. If $x_{1}+\ldots+x_{k}\leq 1$, then we know that the gain of the
algorithm is $x_{k}+(1-\alpha)(x_{1}+\ldots+x_{k-1})$, which is larger than
$1/(2+\alpha)$ by construction.

Otherwise, $x_{1}+\ldots+x_{k}>1$. In this case, if all of the elements of the
request sequence are small or there is at most one large element, we are in
the same case as before and we obtain the desired competitive ratio. Let us
now assume that we have two large elements in our request sequence. We know
that $x_{1}<\frac{1}{2+\alpha}$ and $x_{2}<1/(2+\alpha)-(1-\alpha)x_{1}$. By
Lemma 6, we can also assume that $x_{1}\geq x_{2}$ and with this we can deduce
that $x_{2}<\frac{1}{(2+\alpha)}-(1-\alpha)x_{2}$ and thus
$(2-\alpha)x_{2}<\frac{1}{(2+\alpha)}$ which allows us to estimate $x_{2}$ as
$x_{2}<\frac{1}{(2+\alpha)(2-\alpha)}$ Now, we can fall in one of the
following cases:

  1. 1.

If $x_{1}+x_{2}+x_{k}\leq 1$, filling up greedily from the small items, we
obtain the desired competitive ratio.

  2. 2.

If $x_{1}+x_{2}+x_{k}>1$, but $x_{1}+x_{k}\leq 1$, we pack $x_{1}$ and $x_{k}$
and pack the small items greedily. If the small items fill the knapsack until
at least $\frac{1}{(2+\alpha)(1-\alpha)}$, we know that we obtain the desired
competitive ratio. Otherwise, the gain obtained by the algorithm is

$\displaystyle x_{1}+x_{3}+\ldots+x_{k}-\alpha(x_{1}+\ldots+x_{k-1})$
$\displaystyle=x_{k}+(1-\alpha)(x_{1}+x_{3}+\ldots+x_{k-1})-\alpha x_{2}$
$\displaystyle>1-x_{1}-x_{2}+(1-\alpha)x_{1}-\alpha
x_{2}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$ $\displaystyle=1-\alpha
x_{1}-(1+\alpha)x_{2}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$
$\displaystyle>1-\frac{\alpha}{2+\alpha}-\frac{1+\alpha}{(2+\alpha)(2-\alpha)}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$
$\displaystyle=\frac{(2+\alpha)(2-\alpha)-\alpha(2-\alpha)-(1+\alpha)}{(2+\alpha)(2-\alpha)}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$
$\displaystyle=\frac{3(1-\alpha)}{(2+\alpha)(2-\alpha)}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$
$\displaystyle\geq\frac{1}{2+\alpha}+(1-\alpha)(x_{3}+\ldots+x_{k-1})\;.$

where the last step is true for any $\alpha\leq 1/2$, and we used
$x_{k}>1-x_{1}-x_{2}$ and the upper bounds $x_{1}<\frac{1}{2+\alpha}$ and
$x_{2}<\frac{1}{(2+\alpha)(2-\alpha)}$ for $x_{1}$ and $x_{2}$.

  3. 3.

If $x_{1}+x_{k}>1$, but $x_{2}+x_{k}\leq 1$, we pack $x_{2}$ and $x_{k}$ into
the knapsack and the small items greedily. Here, again, if the small items
fill the knapsack until at least $\frac{1}{(2+\alpha)(1-\alpha)}$, we know
that we obtain the desired competitive ratio, otherwise, the gain obtained by
the algorithm is $x_{2}\ldots+x_{k}-\alpha(x_{1}+\ldots+x_{k-1})$ which is
exactly the same as in the case for $\alpha\leq\alpha_{4}$, and we can perform
the same operations and obtain the desired bound for the competitive ratio.

  4. 4.

If $x_{2}+x_{k}>1$, we pack $x_{k}$ into the knapsack and pack the small items
greedily. If these fill the knapsack with at least
$\frac{1}{(2+\alpha)(1-\alpha)}$, we know that we obtain the desired
competitive ratio, otherwise, the gain obtained by the algorithm is

$\displaystyle x_{3}+\ldots+x_{k}-\alpha(x_{1}+\ldots+x_{k-1})$
$\displaystyle=x_{k}+(1-\alpha)(x_{3}+\ldots+x_{k-1})-\alpha x_{2}-\alpha
x_{1}$ $x_{k}>1-x_{2}$, remove $(1-\alpha)x_{1}$ $\displaystyle\geq
1-x_{2}-\alpha x_{1}-\alpha x_{2}+(1-\alpha)(x_{3}+\ldots+x_{k-1})$
$\displaystyle=1-\alpha
x_{1}-(1+\alpha)x_{2}+(1-\alpha)(x_{3}+\ldots+x_{k-1})\;,$

which is exactly the same as in the case where $x_{1}+x_{2}+x_{k}>1$ but
$x_{1}+x_{k}\leq 1$.

∎

We continue with proving an upper bound for the rest of the interval, using
induction over the number of large elements. Before we start our proof, we
provide a lemma that allows us to ignore possible small elements during the
proof of Theorem 3.

######  Lemma 8.

Given a request sequence without small elements for which Algorithm 2 does not
achieve a competitive ratio of $2+\alpha$, adding small elements to it will
only improve its competitive ratio.

###### Proof.

Let us consider a request sequence containing only large elements
$x_{1}\geq\ldots\geq x_{k-1},x_{k},\ldots,x_{n}$, where $x_{k}$ is the element
triggering the packing for Algorithm 2, and for which the achieved competitive
ratio is larger than $2+\alpha$. This means, by Lemma 5, that the total size
of the items packed into the knapsack is smaller than
$1/(2+\alpha)(1-\alpha)$. By definition, if we add enough small elements to
the request sequence before $x_{k}$, the small elements can be packed greedily
until the knapsack is filled up to $1/(2+\alpha)(1-\alpha)$, achieving the
desired competitive ratio. If not enough of them are added before $x_{k}$, the
small elements requested before $x_{k}$ will be reserved but will still be
able to be packed, so they will never contribute negatively to the total
packing gain. ∎

This lemma brings us to the point where it is possible to prove Theorem 3.

###### Proof of Theorem 3.

We prove by induction that, for any finite number of large elements before the
packing, Algorithm 2 achieves the desired competitive ratio for
$\alpha<\phi-1$. The base case for zero large elements is trivial, as we can
greedily reserve and later pack all small elements to get the desired
competitive ratio. Let us assume that Algorithm 2 achieves the desired
competitive ratio for any request sequence with less than $k-1$ large elements
before the algorithm packs and stops.

If a request sequence has $k-1$ large elements, we can assume by Lemma 6 that
the smallest of those is $x_{k-1}$, and we can also assume by Lemma 8 that
$x_{k}$ triggers the packing. Let us assume, using Lemma 10, that we have an
instance $x_{1}\geq x_{2}\geq\ldots\geq x_{k-1},x_{k},\ldots x_{n}$. Moreover,
note that

$\displaystyle\frac{\alpha}{1-\alpha}$ $\displaystyle<1-\alpha\text{ for
}\alpha<\phi-1\;..$ (17)

We distinguish two cases.

  1. 1.

Assume that, when the packing is triggered, $x_{k-1}$ is not part of an
optimal packing.

In this case,

$\biggl{(}\sum_{i\text{ is packed}}x_{i}\biggr{)}+x_{k-1}>1\;.$ (18)

We also have

$\displaystyle x_{k-1}+(1-\alpha)\sum_{j<k-1}x_{j}$
$\displaystyle<\frac{1}{2+\alpha}\;,$ (19)

since $x_{k-1}$ would trigger the packing otherwise, and thus

$\displaystyle x_{k-1}$ $\displaystyle<\frac{1}{2+\alpha}\;.$ (20)

Thus, the gain that Algorithm 2 achieves is

$\displaystyle\biggl{(}\sum_{j\text{ is packed}}x_{j}\biggr{)}-\alpha R$
$\displaystyle>1-x_{k-1}-\alpha\sum_{j\leq k-1}x_{j}$ using (18)
$\displaystyle=1-(1+\alpha)x_{k-1}-\alpha\sum_{j<k-1}x_{j}$
$\displaystyle=1-2\alpha
x_{k-1}-(1-\alpha)\biggl{(}x_{k-1}+\frac{\alpha}{1-\alpha}\sum_{j<k-1}x_{j}\biggr{)}$
$\displaystyle\geq 1-2\alpha
x_{k-1}-(1-\alpha)\biggl{(}x_{k-1}+(1-\alpha)\sum_{j<k-1}x_{j}\biggr{)}$ using
(17) $\displaystyle\geq 1-2\alpha x_{k-1}-(1-\alpha)\frac{1}{2+\alpha}$ using
(19) $\displaystyle>1-\frac{2\alpha}{2+\alpha}-\frac{1-\alpha}{2+\alpha}$
using (20) $\displaystyle=\frac{1}{2+\alpha}\;,$

as we wanted.

  2. 2.

Assume that when the packing is triggered, $x_{k-1}$ is part of an optimal
packing. We consider two subcases.

    1. (a)

Taking $x_{k-1}$ out of the request sequence still triggers the packing.

This means that $x_{k}+(1-\alpha)(R-x_{k-1})\geq\frac{1}{2+\alpha}$ holds. We
can thus consider the sequence $x_{1},\ldots,x_{k-2},x_{k}$. This sequence has
$k-2$ large elements, and $x_{k-1}$ cannot be part of its optimal solution,
thus its competitive ratio is at most $2+\alpha$ by the induction hypothesis,
and the competitive ratio after adding $x_{k-1}$ can only get better.

    2. (b)

Taking $x_{k-1}$ out of the request sequence does not trigger the packing.

This means that

$\displaystyle x_{k}+(1-\alpha)(R-x_{k-1})<\frac{1}{2+\alpha}\;,$ and also
(21) $\displaystyle x_{k}+(1-\alpha)R\geq\frac{1}{2+\alpha}\;,$ (22)

and, if we let $x_{t}$ be the smallest element that does not get packed,
$x_{t}\geq x_{k-1}$ holds. Also, because of the optimality of the packing
$x_{k}\geq x_{t}$, (otherwise one can take all of the reserved elements as the
packing and obtain a better bound) and

$\sum_{j\text{ is packed}}x_{j}-x_{k-1}+x_{t}>1\;$ (23)

holds. With these bounds, the gain incurred by the algorithm is at least

$\displaystyle\biggl{(}\sum_{j\text{ is packed}}x_{j}\biggr{)}-\alpha R$
$\displaystyle>1-x_{t}+x_{k-1}-\alpha R$ using (23)
$\displaystyle>1-x_{t}+\frac{x_{k}}{1-\alpha}+R-\frac{1}{(1-\alpha)(2+\alpha)}-\alpha
R$ using (21)
$\displaystyle=1-x_{t}+\frac{x_{k}}{1-\alpha}+(1-\alpha)R-\frac{1}{(1-\alpha)(2+\alpha)}$
$\displaystyle\geq 1-x_{t}+\frac{\alpha
x_{k}}{1-\alpha}+\frac{1}{2+\alpha}-\frac{1}{(1-\alpha)(2+\alpha)}$ using (22)
$\displaystyle=\frac{1}{2+\alpha}+\frac{1-\alpha-\alpha^{2}}{(1-\alpha)(2+\alpha)}-x_{t}+\frac{\alpha
x_{k}}{1-\alpha}$
$\displaystyle\geq\frac{1}{2+\alpha}+\frac{1-\alpha-\alpha^{2}}{(1-\alpha)(2+\alpha)}+\frac{\alpha-(1-\alpha)}{1-\alpha}x_{k}$
$\displaystyle\text{using }x_{k}\geq x_{t}$
$\displaystyle=\frac{1}{2+\alpha}+\frac{1-\alpha-\alpha^{2}}{(1-\alpha)(2+\alpha)}+\frac{2\alpha-1}{1-\alpha}x_{k}$
$\displaystyle\geq\frac{1}{2+\alpha}\;,$

where the last step is trivially true for any $\alpha\geq 1/2$. Thus we get
the desired competitive ratio in the considered range for $\alpha$.

This proves the induction step, and thus the desired upper bound on the
competitive ratio. ∎

###  2.3 Upper Bound for $\phi-1\leq\alpha<1$

For proving an upper bound, we consider Algorithm 3 and first bound its
reservation costs.

$R:=0$;

for $k=1,\ldots,n$ do

if $x_{k}+(1-\alpha)R\geq 1-\alpha$ then

pack $x_{1},\ldots,x_{k}$ optimally;

stop

else

reserve $x_{k}$;

$R:=R+x_{k}$

pack $x_{1},\ldots,x_{n}$ optimally

Algorithm 3 Algorithm for $\phi-1\leq\alpha<1$

######  Lemma 9.

For Algorithm 3, the reservation cost $R$ is never larger than $1$.

###### Proof.

For any $j$, let $R_{j}$ denote the reservation cost of the algorithm after
the items $x_{1},\ldots,x_{j}$ have been presented. If, for any $k$,

$x_{k}+(1-\alpha)R_{k-1}<1-\alpha\;,$

then the algorithm reserves the item $x_{k}$ and has a new reservation cost of
$R_{k}=x_{k}+R_{k-1}$. Since obviously $x_{k}\geq(1-\alpha)x_{k}$, we have

$(1-\alpha)R_{k}=(1-\alpha)x_{k}+(1-\alpha)R_{k-1}\leq
x_{k}+(1-\alpha)R_{k-1}<1-\alpha\;.$

Thus, $R_{k}<1$. Because we can apply this reasoning to any $x_{k}$ that does
not trigger the if-condition in the algorithm, we have proven the claim. ∎

And we also need a lemma, analogous to Lemma 6, allowing us to reorder the
items,

######  Lemma 10.

If $x_{1},\ldots,x_{n}$ is an instance for Algorithm 3, whose packing is
triggered by $x_{k}$, with a competitive ratio larger than
$\frac{1}{1-\alpha}$, then there is another instance
$x_{i_{1}},x_{i_{2}},x_{i_{3}},\ldots,x_{i_{k-1}},\allowbreak
x_{k},\ldots,x_{n}$ where $(i_{1},i_{2},\ldots,i_{k-1})$ is a permutation of
$(1,\ldots,k-1)$ and $x_{i_{1}}\geq x_{i_{2}}\geq\ldots\geq x_{i_{k-1}}$, that
also has a competitive ratio larger than $\frac{1}{1-\alpha}$.

###### Proof.

We show how to transform the original sequence such that the number of
inversions is reduced by one. Repeating this transformation yields the desired
result.

Let $x_{1},\ldots,x_{n}$ be an instance for Algorithm 3, such that packing is
triggered by $x_{k}$ with a competitive ratio larger than
$\frac{1}{1-\alpha}$. Assume that $x_{i}<x_{i+1}$ for some $i<k-1$. We prove
that we will get again an instance with a competitive ratio larger than
$\frac{1}{1-\alpha}$ if we swap the positions of $x_{i}$ and $x_{i+1}$. It is
easy to see that this transformation preserves the sum of the first $k-1$
items. To show that it is a sequence that does not trigger the packing after
the $i$th or $(i+1)$st item, we have to verify that

$x_{i+1}<(1-\alpha)-(1-\alpha)(x_{1}+\cdots+x_{i-1})$ (24)

and

$x_{i}<(1-\alpha)-(1-\alpha)(x_{1}+\cdots+x_{i-1}+x_{i+1})\;.$ (25)

Here, (24) is straightforward, since $x_{k}$ for $k>i+1$ triggering the
packing in the unmodified instance implies
$x_{i+1}<(1-\alpha)-(1-\alpha)(x_{1}+\cdots+x_{i})$. We prove (25) by means of
a contradiction. Assume, that

$x_{i}\geq(1-\alpha)-(1-\alpha)(x_{1}+\cdots+x_{i-1}+x_{i+1})\;.$ (26)

We also know that, for $1\leq j\leq i+1$,

$x_{j}\leq(1-\alpha)-(1-\alpha)(x_{1}-\ldots-x_{j-1})\;,$ (27)

and by construction

$x_{i}<x_{i+1}\;.$ (28)

If we define $z=(1-\alpha)-(1-\alpha)(x_{1}+\cdots+x_{i-1})$, then we can
rewrite (26), (27) for $j=i+1$, and (28) as

$\displaystyle x_{i}$ $\displaystyle\geq z-\textstyle(1-\alpha)x_{i+1},$
$\displaystyle x_{i+1}$ $\displaystyle\leq z-\textstyle(1-\alpha)x_{i},$
$\displaystyle x_{i}$ $\displaystyle<x_{i+1}\;.$

As in the proof of Lemma 6, we can solve this system of equations and conclude
that the first two conditions are only satisfiable if $x_{i+1}\leq x_{i}$,
which gives us the desired contradiction.

Thus, the new sequence has a competitive ratio larger than
$\frac{1}{1-\alpha}$. Again, although the order of $x_{1},\ldots,x_{k-1}$ has
been changed, the same reserved requests trigger a packing with $x_{k}$ with
the same reservation size, just as before the transformation. Hence, if there
was no way to pack the items well enough before the transformation, it also
cannot be done afterwards. ∎

We are now ready to prove the desired competitive ratio for Algorithm 3.

######  Theorem 11.

Algorithm 3 is an online algorithm for ReserveKP achieving a competitive ratio
of at most $\frac{1}{1-\alpha}$, for all $\phi-1\leq\alpha<1$.

###### Proof.

Let us first assume that we run Algorithm 3 on an instance
$x_{1},\ldots,x_{n}$, and no element triggers the packing. This means that all
elements are reserved. But we know by Lemma 9 that the reservation never
exceeds the capacity of the knapsack. This means that the optimal solution
packs all offered elements. Thus, the algorithm achieves a competitive ratio
of

$\frac{\sum_{i=1}^{n}x_{k-1}}{\sum_{i=1}^{n}x_{k-1}-\alpha\sum_{i=1}^{n}x_{k-1}}=\frac{1}{1-\alpha}\;.$

Now, it remains to analyze the case where an instance $x_{1},\ldots,x_{n}$
triggers the packing, for some $x_{k}$. Let us do an induction on the value of
$k$. If $k=1$, the first item offered triggers the packing, thus it holds that
$x_{1}\geq 1-\alpha$ and the gain of the algorithm is at least $1-\alpha$ as
we expected. Now, we assume that Algorithm 3 has a gain of at least $1-\alpha$
on any request sequence triggering the algorithm to pack and stop before $k$
elements are offered.

We proceed similarly to the proof of Theorem 3. Let us assume, using Lemma 10,
that we have an instance $x_{1}\geq x_{2}\geq\ldots\geq x_{k-1},x_{k},\ldots
x_{n}$ where the algorithm packs after receiving $x_{k}$. We distinguish two
cases.

  1. 1.

When the packing is triggered, $x_{k-1}$ is not part of an optimal packing.

In this case,

$\displaystyle\biggl{(}\sum_{j\text{ is packed}}x_{j}\biggr{)}+x_{k-1}>1\;.$
(29)

We consider the following bounds. Since $x_{k-1}$ did not trigger the packing,
we know that

$\displaystyle x_{k-1}+(1-\alpha)\sum_{j<k-1}x_{j}$
$\displaystyle<1-\alpha\;,$ (30)

and thus also $x_{k-1}<1-\alpha$.

Thus, the gain that Algorithm 3 achieves is

$\displaystyle\biggl{(}\sum_{j\text{ is packed}}x_{j}\biggr{)}-\alpha R$
$\displaystyle\geq 1-x_{k-1}-\alpha\sum_{j\leq k-1}x_{j}$ using (29)
$\displaystyle=1-(1+\alpha)x_{k-1}-\alpha\sum_{j<k-1}x_{j}$
$\displaystyle>1-(1+\alpha)x_{k-1}-\alpha\biggl{(}1-\frac{x_{k-1}}{1-\alpha}\biggr{)}$
using (30)
$\displaystyle=1-\alpha+\biggl{(}\frac{\alpha}{1-\alpha}-(1+\alpha)\biggr{)}x_{k-1}$
$\displaystyle\geq 1-\alpha+\frac{-1+\alpha+\alpha^{2}}{1-\alpha}x_{k-1}$
$\displaystyle\geq 1-\alpha$ $\displaystyle\text{using $\alpha\geq\phi-1$}\;.$

Thus we obtain the expected gain in this case.

  2. 2.

When the packing is triggered, $x_{k-1}$ is part of an optimal packing. We can
consider two subcases.

    1. (a)

Taking $x_{k-1}$ out of the request sequence still triggers the packing.

This means that

$x_{k}+(1-\alpha)(R-x_{k-1})\geq 1-\alpha\;$

holds. We can thus consider the sequence $x_{1},\ldots,x_{k-2},x_{k}$. This
sequence has $k-1$ items before the packing is triggered, and $x_{k-1}$ cannot
be part of its optimal solution, thus its competitive ratio is at most
$1/(1-\alpha)$ by the induction hypothesis, and the competitive ratio after
adding $x_{k-1}$ can only get better.

    2. (b)

Taking $x_{k-1}$ out of the request sequence does not trigger the packing.

This means that

$\displaystyle x_{k}+(1-\alpha)(R-x_{k-1})<1-\alpha\;,$ (31)

but also

$\displaystyle x_{k}+(1-\alpha)R\geq 1-\alpha\;,$ (32)

and, if we let $x_{j}$ be the smallest element that does not get packed,
$x_{j}\geq x_{k-1}$ holds. Also because of the optimality of the packing,
$x_{k}\geq x_{j}$ (otherwise one can take all of the reserved elements as the
packing and obtain a better bound) and it holds that

$\displaystyle\biggl{(}\sum_{t\text{ is
packed}}x_{t}\biggr{)}-x_{k-1}+x_{j}>1\;.$ (33)

Moreover, we can bound $x_{j}\leq x_{1}\leq 1-\alpha$. With these bounds, the
gain incurred by the algorithm is at least

$\displaystyle\biggl{(}\sum_{t\text{ is packed}}x_{t}\biggr{)}-\alpha R$
$\displaystyle\geq 1-x_{j}+x_{k-1}-\alpha R$ using (33) $\displaystyle\geq
1-x_{j}+\frac{x_{k}}{1-\alpha}+R-1-\alpha R$ using (31)
$\displaystyle=-x_{j}+\frac{\alpha}{1-\alpha}x_{k}+x_{k}+(1-\alpha)R$
$\displaystyle\geq-x_{j}+\frac{\alpha}{1-\alpha}x_{k}+(1-\alpha)$ using (32)
$\displaystyle=1-\alpha-x_{j}+\frac{\alpha}{1-\alpha}x_{k}$ $\displaystyle\geq
1-\alpha-x_{j}+\frac{\alpha}{1-\alpha}x_{j}$ $\displaystyle x_{k}\geq x_{j}$
$\displaystyle=1-\alpha+\frac{2\alpha-1}{1-\alpha}x_{j}$ $\displaystyle\geq
1-\alpha$

as we wanted.

This proves the induction step, and thus the desired competitive ratio upper
bound. ∎

We continue by providing matching lower bounds to the upper bounds of this
section.

##  3 Lower Bounds

First we present an adversarial strategy that works for all values of
$\alpha$. Then we proceed to analyze the case where only four objects are
presented as a generic adversarial strategy and find improved lower bounds for
some values of $\alpha$.

###  3.1 Tight Lower Bound for $0\leq\alpha\leq 0.25$

######  Theorem 12.

For $\alpha>0$ there exists no algorithm for reservation knapsack achieving a
competitive ratio better than $2$.

###### Proof.

Consider the following set of adversarial instances as depicted in Figure 2.
Given any $\varepsilon>0$, the adversary presents first an object of size
$\frac{1}{2}+\delta$ with $0<\delta\ll\varepsilon$. If an algorithm takes this
object, an object of size 1 will follow, making its competitive ratio
$1/(\frac{1}{2}+\delta)>2-\varepsilon$. If an algorithm rejects this object,
no more objects will follow and it will not be competitive. If an algorithm
reserves this object, then an object of size $\frac{1}{2}+\delta^{2}$ will be
presented. Observe, that these two objects do not fit together into the
knapsack. If an algorithm takes this object, an object of size $1$ will be
presented, and again the algorithm will achieve a competitive ratio worse than
$2-\varepsilon$. If an algorithm rejects this object, then an object of size
$\frac{1}{2}-\delta^{2}$ will be presented. This object does not fit in the
knapsack with the first one, thus the algorithm can only pack the first
object, obtaining a competitive ratio worse than $2-\varepsilon$. If an
algorithm reserves it instead, an object of size $\frac{1}{2}+\delta^{3}$ will
be presented. The adversary can follow this procedure on and on, and in each
step the competitive ratios for algorithms that accept or reject the offered
item only get worse due to the additional reservation costs.

The adversary can stop offering items as soon as the reservation costs are
such that filling the knapsack will only result in a competitive ratio worse
than $2$. This shows that, for every $\varepsilon>0$, the competitive ratio is
at least $2-\varepsilon$, so the best competitive ratio is at least $2$. ∎

$x_{1}=\frac{1}{2}+\delta$$x_{2}=1$,
end${\rho}_{{\mathtt{A}}}>2-\varepsilon$end${\rho}_{{\mathtt{A}}}>2$$x_{2}=\frac{1}{2}+\delta^{2}$$x_{3}=1$,
end${\rho}_{{\mathtt{A}}}>2$$x_{3}=\frac{1}{2}-\delta^{2}$,
end${\rho}_{{\mathtt{A}}}=\frac{1}{(1-\alpha)(\frac{1}{2}+\delta)}>2$$x_{3}=\frac{1}{2}+\delta^{3}$$\ldots$rejecttakereserverejecttakereserve
Figure 2: Sketch of the adversarial strategy that is used in the proof of
Theorem 12.

The adversarial strategy depicted in Figure 2 works for every positive value
of $\alpha$, but is of course not tight when $\alpha>0.25$. Observe that, if
an algorithm continues to reserve items, the cumulated reservation cost will
eventually exceed any remaining gain.

###  3.2 Tight Lower Bound for $0.25\leq\alpha\leq 1$

The previous strategy provided us with a lower bound that does not match the
upper bound for $\alpha>0.25$. We improve the lower bound for larger $\alpha$
in a way that it provides a matching bound by designing a generic adversarial
strategy with up to four items as shown in Figure 3, which contains the
competitive ratios for all possible outcomes. For each item, an algorithm can
decide to either reject, pack or reserve it. Depending on an algorithm’s
behavior on the previous item, it is decided whether another item is presented
and, if so, which item. We assume by construction that $s<t<u<1$ and $s+t>1$.
The competitive ratio of such a strategy is therefore bounded by

${\rho}_{{\mathtt{A}}}\geq\min\Bigl{\\{}\frac{1}{s},~{}\frac{t}{(1-\alpha)s},~{}\frac{1}{t-\alpha
s},~{}\frac{u}{t-\alpha(s+t)},~{}\frac{1}{u-\alpha(s+t)},~{}\frac{u}{u-\alpha(s+t+u)}\Bigr{\\}}.$
(34)

To prove a lower bound for every $0<\alpha<1$, we can choose $s$, $t$ and $u$
in order to make (34) as large as possible. Standard calculus leads to the
bounds in the following theorem.

$x_{1}=s$$x_{2}=1$,
end${\rho}_{{\mathtt{A}}}=\frac{1}{s}$end${\rho}_{{\mathtt{A}}}=\infty$$x_{2}=t$$x_{3}=1$,
end${\rho}_{{\mathtt{A}}}=\frac{1}{t-\alpha
s}$end${\rho}_{{\mathtt{A}}}=\frac{t}{(1-\alpha)s}$$x_{4}=u$$x_{4}=1$,
end${\rho}_{{\mathtt{A}}}=\frac{1}{u-\alpha(s+t)}$end${\rho}_{{\mathtt{A}}}=\frac{u}{t-\alpha(s+t)}$end${\rho}_{{\mathtt{A}}}=\frac{u}{u-\alpha(s+t+u)}$rejecttakereserverejecttakereserverejecttakereserve
Figure 3: Diagram of a generic adversarial strategy with 4 items where
$s<t<u<1$ and $s+t>1$.

######  Theorem 13.

The competitive ratio of ReserveKP is at least

###### Proof.

Let us consider an adversary that presents an item of size $s$ first. The size
of this item has to be smaller than $\frac{1}{2}$, otherwise an algorithm can
take this item and get a competitive ratio smaller than $2$. If $s$ is taken,
the adversary presents an item of size $1$. If $s$ is rejected, no more items
will be offered. If $s$ is reserved, an item of size $t$ is presented, where
$s+t>1$. If $t$ is taken, the adversary presents an item of size $1$ and if
$t$ is rejected, no more items will be offered, and, if $t$ is reserved, an
item of size $u$ is presented with $u>t$, if $u$ is taken, the adversary
presents an item of size $1$ and otherwise the request sequence ends in this
third item.

For this adversarial strategy, we can compute the competitive ratio for all
possible algorithms as can be seen in Figure 3.

Thus, the competitive ratio of any algorithm ${\mathtt{A}}$ confronted with
this adversary is bounded by Equation (34), which we want to maximize.

Choosing $s=\frac{2}{3+\sqrt{5-4\alpha}}+\varepsilon$,
$t=\frac{\sqrt{5-4\alpha}-1+2\alpha}{2(1+\alpha)}$, and
$u=\frac{\alpha+\sqrt{4(t-\alpha)+\alpha^{2}}}{2}$, we see that, if
$0.225\leq\alpha\leq\sqrt{2}-1$, then
${\rho}_{{\mathtt{A}}}\geq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$.

If we compare the given competitive ratio to all of the expressions from (34),
and substitute the values of $s$, $t$ and $u$ but omit the $\varepsilon$ in
the $s$, we see immediately that
$1/s=\frac{3+\sqrt{5-4\alpha}}{2}\geq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$
for $\alpha\leq\sqrt{2}-1$, and $\frac{1}{t-\alpha
s}=\frac{t}{s-\alpha(s+t)}=\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$.

The last three expressions are $\frac{1}{u-\alpha}$, $\frac{u}{t-\alpha}$ and
$\frac{u}{u(1-\alpha)-\alpha}$. For the given $u$, we see that
$\frac{1}{u-\alpha}=\frac{u}{t-\alpha}\geq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$
for $\alpha\geq\alpha_{0}$, where $\alpha_{0}\approx 0.224$ is the unique
positive root of $x^{4}+2x^{3}-2x^{2}+5x-1$. Finally, we observe that
$\frac{u}{u(1-\alpha)-\alpha}\geq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ for
$\alpha\geq 0.19$ and in particular through the desired range.

Note that $2\geq\frac{1+\sqrt{5-4\alpha}}{2(1-\alpha)}$ for $\alpha\leq 0.25$,
so while the lower bound is correct for values of $\alpha$ down to
approximately $0.224$, our previous lower bound dominates it up to
$\alpha=0.25$.

For the range of $\sqrt{2}-1\leq\alpha\leq\phi-1$, we choose
$s=\frac{1}{2+\alpha}$, $t=1-s+\varepsilon$ and no element $u$. We can rewrite
Equation (34) as

${\rho}_{{\mathtt{A}}}\geq\min\Bigl{\\{}\frac{1}{s},~{}\frac{1}{t-\alpha
s},~{}\frac{1}{t-\alpha s},~{}\frac{t}{t-\alpha(s+t)}\Bigr{\\}}.$ (35)

Substituting the appropriate values of $s$ and $t$ in Equation (35) yields

${\rho}_{{\mathtt{A}}}\geq\min\Bigl{\\{}2+\alpha,\frac{1+\alpha}{1-\alpha},\frac{1+\alpha}{1-\alpha-\alpha^{2}}\Bigr{\\}}.$

But $\frac{1+\alpha}{1-\alpha}\geq 2+\alpha$ for $\alpha\geq\sqrt{2}-1$ and
$\frac{1+\alpha}{1-\alpha-\alpha^{2}}\geq\frac{1+\alpha}{1-\alpha}$ as long as
the denominator is not negative, that is, as long as $\alpha\leq\phi-1$.

Finally, for the range $\phi-1\leq\alpha\leq 1$, we choose $s=1-\alpha$ and no
elements $t$ or $u$. We can rewrite Equation (34) as

${\rho}_{{\mathtt{A}}}\geq\min\Bigl{\\{}\frac{1}{s},~{}\frac{s}{s-\alpha
s}\Bigr{\\}}.$ (36)

Substituting the appropriate values of $s$ in Equation (36) yields
${\rho}_{{\mathtt{A}}}\geq\frac{1}{1-\alpha}$ as expected. ∎

##  4 Nonrejecting Algorithms

A seemingly plausible intuition for ReserveKP might be the following: If the
cost of reservation is very small, rejecting an item should not be necessary,
as even when an item cannot be packed, the cost of reserving it is negligible.
On the other hand, when the reservation cost is rising, aggressively reserving
items may seem like a very bad strategy, as the risk of not being able to
utilize reserved items may come to mind. Interestingly, both of these
intuitions turn out to be wrong, which we will show by first giving a lower
bound for nonrejecting algorithms (i.e., algorithms that reject nothing until
they pack the knapsack, after which all remaining items are rejected) that
exceeds the upper bound of a rejecting algorithm for small $\alpha$ and that
tightly matches the upper bound of a nonrejecting algorithm for bigger
$\alpha$.

We first provide a lower bound for algorithms that are unable to reject items.

$x_{1}=\frac{1}{2+\alpha}$$x_{2}=1$,
end${\rho}_{{\mathtt{A}}}=2+\alpha$$x_{2}=\frac{1+\alpha}{2+\alpha}+\varepsilon$$x_{3}=1$,
end${\rho}_{{\mathtt{A}}}=2+\alpha$$x_{3}=\frac{1+\alpha}{2+\alpha}+\varepsilon$${\rho}_{{\mathtt{A}}}>2+\alpha$$\ldots$$\ldots$takereservetakereserve
Figure 4: Sketch of the adversarial strategy that is used in the proof of
Theorem 14. Upon continued reservation, a new item of the same size is
presented repeatedly.

######  Theorem 14.

There exists no deterministic online algorithm for ReserveKP that does not
reject any elements with a competitive ratio better than $2+\alpha$ for any
$0<\alpha\leq 1$.

###### Proof.

Let $\varepsilon>0$. Consider the following set of adversarial instances
depicted in Figure 4. First the adversary presents an item of size
$\frac{1}{2}-\frac{\alpha}{4+2\alpha}=\frac{1}{2+\alpha}$. If an algorithm
takes this item the adversary will present an item of size 1, and the
algorithm will have a competitive ratio of $2+\alpha$ as claimed. If an
algorithm reserves this first item, the adversary will present a second item
of size
$\frac{1}{2}+\frac{\alpha}{4+2\alpha}+\varepsilon=\frac{1+\alpha}{2+\alpha}+\varepsilon$.
As both items do not fit into the knapsack together, an algorithm can decide
to either take the larger of the two items or to reserve this second item as
well. If it takes the larger item, the adversary will again present an item of
size one. An algorithm can thus achieve a gain of

$\frac{1+\alpha}{2+\alpha}+\varepsilon-\alpha\frac{1}{2+\alpha}=\frac{1}{2+\alpha}+\varepsilon$

which results in the claimed competitive ratio. Finally, whenever an algorithm
decides to reserve an item, from this point onwards, another item of size
$\frac{1+\alpha}{2+\alpha}+\varepsilon$ is presented. At any point at which
the algorithm decides to take a presented item, an item of size 1 is presented
afterwards. As there are no two items in the instance that fit into the
knapsack together, the gain of any deterministic nonrejecting algorithm will
strictly decrease with every reservation. ∎

Combined with the upper bound given in Theorem 1, we see that an algorithm
that is unable to reject items performs quite a bit worse than one that is
able to reject items, such as Algorithm 1. Thus, an algorithm needs to be able
to reject items to become 2-competitive for small values of $\alpha$. On the
other hand, the lower bound provided in Theorem 14 matches the upper bound of
Theorem 2, which is based on the nonrejecting Algorithm 2. We conjecture that
there are nonrejecting algorithms for every $\alpha\geq\sqrt{2}-1$ that are at
least as good as any other algorithms that are able to reject items.

##  5 Further Work

In this work, we provide tight competitive ratios for the ReserveKP. While the
model seems natural to analyze, there are possible variations that could be
studied in order to see how a variation of the reservation model influences
the competitive ratio. One could consider a variant where reservation costs
are refunded if the item is used, modelling real-world applications such as a
down payment. Another reasonable model could look at the largest sum of items
in a reserve at any time and ask for reservation costs relative to this size,
such as when companies have to rent storage space.

The concept of reservation may be applied to other online problems such as
online call admission problems in networks [2, 7, 19] or problems of embedding
guest graphs into a host graph. In the online path packing problem, one packs
paths in a edge-disjoint way (sometimes node-disjointly) into a graph, which
is a generalization of ReserveKP, thus inheriting all lower bounds. The
offline version was studied on many types of graphs, with an incomplete
selection being [10, 21, 23, 8]. The challenge when applying the idea of
reservation is to find an appropriate cost function that can be measured
against the competitive ratio.

## References

  * [1] Susanne Albers.  Energy-efficient algorithms.  Commun. ACM, 53(5):86–96, 2010.  doi:10.1145/1735223.1735245.
  * [2] Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin.  Throughput-competitive on-line routing.  In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 32–40. IEEE Computer Society, 1993.  doi:10.1109/SFCS.1993.366884.
  * [3] Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkovic, Henri Lotze, and Peter Rossmanith.  Online simple knapsack with reservation costs.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16–19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 16:1–16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.STACS.2021.16.
  * [4] Hans-Joachim Böckenhauer, Richard Dobson, Sacha Krug, and Kathleen Steinhöfel.  On energy-efficient computations with advice.  In Dachuan Xu, Donglei Du, and Ding-Zhu Du, editors, Computing and Combinatorics - 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings, volume 9198 of Lecture Notes in Computer Science, pages 747–758. Springer, 2015.  doi:10.1007/978-3-319-21398-9_58.
  * [5] Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke.  Online algorithms with advice: The tape model.  Inf. Comput., 254:59–83, 2017.  doi:10.1016/j.ic.2017.03.001.
  * [6] Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, and Peter Rossmanith.  The online knapsack problem: Advice and randomization.  Theor. Comput. Sci., 527:61–72, 2014.  doi:10.1016/j.tcs.2014.01.027.
  * [7] Allan Borodin and Ran El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, 1998.
  * [8] Darryn E. Bryant.  Packing paths in complete graphs.  J. Comb. Theory, Ser. B, 100(2):206–215, 2010.  doi:10.1016/j.jctb.2009.08.004.
  * [9] Stefan Dobrev, Rastislav Královič, and Dana Pardubská.  Measuring the problem-relevant information in input.  ITA, 43(3):585–613, 2009.  doi:10.1051/ita/2009012.
  * [10] András Frank.  Packing paths in planar graphs.  Combinatorica, 10(4):325–331, 1990.  doi:10.1007/BF02128668.
  * [11] Xin Han, Yasushi Kawase, and Kazuhisa Makino.  Online unweighted knapsack problem with removal cost.  Algorithmica, 70(1):76–91, 2014.  doi:10.1007/s00453-013-9822-z.
  * [12] Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku.  Online knapsack problems with a resource buffer.  In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 28:1–28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ISAAC.2019.28.
  * [13] Juraj Hromkovič, Rastislav Královič, and Richard Královič.  Information complexity of online problems.  In Petr Hliněný and Antonín Kučera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 24–36. Springer, 2010.  doi:10.1007/978-3-642-15155-2_3.
  * [14] Oscar H. Ibarra and Chul E. Kim.  Fast approximation algorithms for the knapsack and sum of subset problems.  J. ACM, 22(4):463–468, 1975.  doi:10.1145/321906.321909.
  * [15] Sandy Irani, Sandeep K. Shukla, and Rajesh Gupta.  Algorithms for power savings.  ACM Trans. Algorithms, 3(4):41, 2007.  doi:10.1145/1290672.1290678.
  * [16] Kazuo Iwama and Shiro Taketomi.  Removable online knapsack problems.  In Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan J. Eidenbenz, and Ricardo Conejo, editors, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, volume 2380 of Lecture Notes in Computer Science, pages 293–305. Springer, 2002.  doi:10.1007/3-540-45465-9_26.
  * [17] Kazuo Iwama and Guochuan Zhang.  Online knapsack with resource augmentation.  Inf. Process. Lett., 110(22):1016–1020, 2010.  doi:10.1016/j.ipl.2010.08.013.
  * [18] Richard M. Karp.  Reducibility among combinatorial problems.  In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [19] Dennis Komm.  An Introduction to Online Computation - Determinism, Randomization, Advice.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2016\.  doi:10.1007/978-3-319-42749-2.
  * [20] Alberto Marchetti-Spaccamela and Carlo Vercellis.  Stochastic on-line knapsack problems.  Math. Program., 68:73–104, 1995.  doi:10.1007/BF01585758.
  * [21] Alexander Schrijver and Paul D. Seymour.  Packing odd paths.  J. Comb. Theory, Ser. B, 62(2):280–288, 1994.  doi:10.1006/jctb.1994.1070.
  * [22] Daniel Dominic Sleator and Robert Endre Tarjan.  Amortized efficiency of list update and paging rules.  Commun. ACM, 28(2):202–208, 1985.  doi:10.1145/2786.2793.
  * [23] Natalia Vanetik.  Path packing and a related optimization problem.  J. Comb. Optim., 17(2):192–205, 2009.  doi:10.1007/s10878-007-9107-z.