Approximating the Incremental Knapsack Problem
Federico Della Crocea,b , Ulrich Pferschyc , Rosario Scatamacchiaa,∗

arXiv:1801.04801v1 [cs.DS] 15 Jan 2018

a

Dipartimento di Ingegneria Gestionale e della Produzione, Politecnico di Torino,
Corso Duca degli Abruzzi 24, 10129 Torino, Italy,
{federico.dellacroce, rosario.scatamacchia}@polito.it
b
CNR, IEIIT, Torino, Italy
c
Department of Statistics and Operations Research, University of Graz,
Universitaetsstrasse 15, 8010 Graz, Austria,
pferschy@uni-graz.at

Abstract
We consider the 0–1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in
a certain period, it cannot be removed afterwards. The contribution of a
packed item in each time period depends on its profit as well as on a time
factor which reflects the importance of the period in the objective function.
The problem calls for maximizing the weighted sum of the profits over the
whole time horizon. In this work, we provide approximation results for IKP
and its restricted variants. In some results, we rely on Linear Programming
(LP) to derive approximation bounds and show how the proposed LP–based
analysis can be seen as a valid alternative to more formal proof systems. We
first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally
applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating
the number of periods is considered as a constant. Then, we add the mild
and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited
for any number of time periods and for the special case with two periods.
Keywords: Incremental Knapsack problem, Approximation scheme,
Linear Programming

∗

Corresponding author.

1. Introduction
The 0–1 Knapsack Problem (KP) is one of the paradigmatic problems
in combinatorial optimization and has been object of numerous publications
and two monographs [20] and [19]. In KP a set of items with given profits
and weights is available and the aim is to select a subset of the items in order
to maximize the total profit without exceeding a known knapsack capacity.
KP is weakly NP-hard, although in practice fairly large instances can be
solved to optimality within limited running time. Various generalizations
of KP have been considered over the years. We mention among others the
most recent contributions we are aware of: the collapsing KP (where the
capacity of the constraint is inversely related to the number of items placed
inside the knapsack) [9]; the discounted KP (where it is required to select a
set of item groups where each group includes three items and at most one of
the three items can be selected) [17]; the parametric KP (where the profits
of the items are affine-linear functions of a real-valued parameter and the
task is to compute a solution for all values of the parameter) [14]; the KP
with setups (where items belong to disjoint families and can be selected only
if the corresponding family is activated) [8, 13, 21]; the penalized KP (where
each item has a profit, a weight, a penalty and the goal is to maximize the
sum of the profits minus the greatest penalty value of the selected items)
[7] and the temporal KP (where a time horizon is considered, and each item
consumes the knapsack capacity during a limited time interval only) [3].
We consider here a very meaningful and natural generalization of KP,
namely the 0–1 Incremental Knapsack Problem (IKP) as introduced in [2]
where the constraining capacity grows over T time periods. If an item is
placed in the knapsack in a certain period, it cannot be removed afterwards.
Each packed item contributes its profit for each time period in which it is
included in the knapsack, with different impacts in the objective function
depending on multiplicative time factors. These reflect the different importance of the periods or allow a discounting over time. The problem calls
for maximizing the weighted sum of the profits accumulated over the whole
time horizon.
IKP generalizes the time-invariant Incremental Knapsack Problem, namely
with unit time multipliers, considered in [15, 16, 23] and which we will denote here as IIKP. IKP has many real-life applications since, from a practical perspective, it is often required in resource allocation problems to deal
with changes in the input conditions and/or in a multi–period optimization
framework. In manufacturing, for instance, a producer may activate contracts with customers for a periodic (e.g. monthly) supply of its products
2

within an expanding production plan. The production capacity is increased
in each time period and the goal is to decide which contracts (and when)
should be set in order to maximize the overall profits over a given time horizon. Here, the increasing capacity values represent the available production
resources in each time period while the items are the orders to satisfy with
corresponding profits and resource consumption. Other applications of an
online IIKP variant in the contexts of renewable resources and of trading
operations are provided in [24].
1.1. Related literature
From a general point of view, [16] introduced incremental versions of
maximum flow, bipartite matching, and also knapsack problems. The authors in [16] discuss the complexity of these problems and show how the
incremental version even of a polynomial time solvable problem, like the
max flow problem, turns out to be NP–hard. General techniques to adapt
the algorithms for the considered optimization problems to their respective
incremental versions are discussed. Also, a general purpose approximation
algorithm is introduced.
In [2], it is shown that even IIKP is strongly NP–hard. A constant factor
algorithm is also provided under mild restrictions on the growth rate of the
knapsack capacity. In addition, a PTAS is√derived for the special variant
IIKP under the assumption that T is in O( log n), where n is the number
of items. In a recent contribution [12], an improved PTAS for IIKP is lined
out. The PTAS in [12] polynomially depends on both n and T without any
further restriction on the input data. Both algorithms introduced in [2] and
[12] cannot be adapted to tackle arbitrary IKP instances. The PTAS derived
in [2] could be extended (for fixed T ) to IKP instances with monotonically
non-increasing time factors. Likewise, the PTAS proposed in [12] can be
extended to IKP instances with monotonically increasing time multipliers.
A number of problems closely related to IKP were tackled in the literature. In [11, 10], a multiperiod variant of the knapsack problem is considered. The capacity increases over periods as in IKP but each item becomes
available for packing only at a certain time period. Thus, the set of items
to choose from increases over time. In [11], a branch and bound algorithm
is proposed. In [10], an efficient algorithm for solving the linear programming relaxation of the problem and a procedure for reducing the number of
variables are presented.
In [24], an online knapsack problem with incremental capacity is considered. In each period a set of items is revealed without knowledge of future
items and the goal is to maximize the overall value of the accepted items.
3

The authors in [24] introduce deterministic and randomized algorithms for
this online knapsack problem and provide an analysis of their performance.
1.2. Our contribution
In this work, we provide approximation results for IKP and its restricted
variants. We employ Linear Programming (LP) to analyze the worst case
performance of different algorithms for deriving approximation bounds. Interestingly, the proposed LP–based analysis can be seen as a valid alternative to formal proof systems based on analytical derivation. Indeed, recently
a growing attention has been centered on the use of LP modeling for the
derivation of formal proofs (see [5, 1]) and we also show here a successful
application of this technique.
In our contribution, in Section 3 we first generalize for IKP the performance analysis of the generic algorithmic approach derived in [16] and
originally applied to IIKP. Moreover, we show the tightness of some approximation ratios provided by the approach, including approximation bounds
derived in [16]. Then, we devise a PTAS in Section 3.2 when the number
of time periods T is a constant. While this is a stronger assumption than
the one made for the PTAS for IIKP in [2] and no assumption on input
T is needed in [12], our algorithm is, to the authors’ knowledge, the first
PTAS that applies to arbitrary IKP instances. Also, the proposed approach
is much simpler and does not require a huge number of complicated LP
models as in [2, 12].
In Section 4 we introduce the natural assumption that each item can be
packed at any point in time, also in the first period. For this reasonable
variant of IKP we discuss two approximation algorithms suited for any T .
Finally, in Section 5 we focus on an IKP variant with T√= 2 and show an
algorithm with an approximation ratio bounded by 21 + 42 = 0.853 . . . and
by 76 = 0.857 . . . for IIKP. A preliminary conference version containing some
of the results of this paper derived for IIKP is presented in [6].
2. Notation and problem formulation
In IKP a set of n items is given together with a knapsack with capacity
values ct for each time period t = 1, . . . , T and increasing over time, i.e.
ct−1 ≤ ct for t = 2, . . . , T . Each item i has a profit pi > 0 and a weight
wi > 0. If an item is placed in the knapsack at time t, it cannot be removed
at a later time. The contribution of an item i at time t is equal to ∆t pi ,
where ∆t > 0 denotes the time multiplier of period t. The problem calls
for maximizing the total profit of the selected items without exceeding the
4

knapsack capacity summing up the profits attained for each time period. In
order to derive an ILP-formulation, we associate with each item i a 0 − 1
variable xit such that xit = 1 iff item i is contained in the knapsack in period
t. IKP can be formulated by the following ILP model:
(IKP)

maximize

T X
n
X

∆t pi xit

(1)

t=1 i=1

subject to

n
X
i=1

wi xit ≤ ct

xi(t−1) ≤ xit
xit ∈ {0, 1}

t = 1, . . . , T ;
i = 1, . . . , n,
i = 1, . . . , n,

(2)
t = 2, . . . , T ;
t = 1, . . . , T.

(3)
(4)

The cost function (1) maximizes the sum of the profits over the time horizon. Constraints (2) guarantee that the items weights sum does not exceed
capacity ct in each period t. Constraints (3) ensure that an item chosen
at time t cannot be removed afterwards. Constraints (4) indicate that all
variables are binary. In IIKP, we have ∆t = 1 for each t = 1, . . . , T .
In the following, we denote by x∗ (resp. z ∗ ) the optimal solution (resp.
solution P
value) of IKP. The contribution of time period t to z ∗ is denoted
by zt∗ = ni=1 ∆t pi x∗it . We also denote by z Y the solution value yielded by
P
a generic algorithm Y and by pcj = Tt=1 ∆t pj xjt the profit contribution of
an item j of a given feasible solution x. For each period t and the related
capacity value ct , we define the corresponding standard knapsack problem
as KPt . This means that in KPt we consider only one of the T constraints
(2). The optimal solution value and related item set of each KPt is denoted
by zt and Sol(KPt ) respectively. Finally,
we define for a generic item
P set S
P
the canonical weight sum w(S) := j∈S wj and profit sum p(S) := j∈S pj .
We say that an approximation algorithm Y has approximation ratio r, for
r ∈ [0, 1), if z Y ≥ r · z ∗ for every instance of IKP.
2.1. IKP Linear Relaxation
The linear relaxation of IKP, where fractions of items can be packed, i.e.
where constraints (4) are replaced by the inclusion in the interval [0, 1], can
be easily computed. In fact, it suffices to order the items by non–increasing
efficiencies wpii in O(n log n) and to fill the capacity of the knapsack in each
period according to this ordering in O(n). Thus, the execution time for

5

solving the linear relaxation of IKP, hereafter denoted by IKPLP , can be
bounded by O(n log n + T ).
An alternative approach would consider each time period t separately
and solve the LP-relaxation for each knapsack problem KPt . Using the
linear-time median algorithm to find the split item, this can be done in
O(n) time for every t = 1, . . . , T , thus requiring O(n · T ) time in total.
Clearly, both approaches deliver exactly the same solution structure. For
small or even constant values of T the latter approach will dominate the
former.
Taking a closer look at the T iterations of this approach one can exploit
the fact that the split item (and thus the LP-relaxation) is always computed
on the same item set, only the capacities change. Avoiding repetitions one
can even get a total running time of O(n log T ). Since T can be expected to
be of moderate size, this is close to a linear time algorithm. The technical
details of this approach can be briefly described as follows:
The classical computation of the split item in linear time requires a sequence of log n iterations (see [19, ch 3.1]). In iteration i for i = 1, . . . , log n,
there are n/2i−1 items considered, their median w.r.t. the efficiencies is computed in O(n/2i−1 ) time, and the considered items are partitioned into two
subsets with efficiencies lower and higher than the median, respectively.
Then, it is determined (in constant time) which of the two subsets contains
the split item and the next iteration is performed on the selected subset
with n/2i items.
Applying this procedure several times for different capacity values on
the same set of items does not change the positions of medians and the
resulting subset structure. Of course, the selections of subsets in each iteration may change for different capacities. Nevertheless, once a certain subset
was considered, its median computed and the partitioning into two halves
performed, this process does not have to be repeated for the same subset
again for a different capacity value. Thus, each subset of size n/2i has to be
processed (in linear time) only once.
We split the analysis of the total effort required for all T capacity values
into two phases. We first consider the iterations i = 1, . . . , log T . In each
such iteration a subset of size n/2i−1 is considered. However, over all T
iterations each item can occur only once in a subset of size n/2i−1 . Thus,
the total effort for the T executions of an iteration indexed by i is bounded
by O(n). The time for this first phase is thus O(n log T ). The running time

6

for the second phase can be simply summed up by
T·

log
Xn

i=log T +1

n
n
≤ T · 2 log T = 2n .
2i−1
2

We summarize our considerations in the following statement.
Theorem 1. The LP-relaxation of IKP can be computed in
O(min{n log T, n log n + T }).
3. Approximating IKP
3.1. Approximation ratios of a general purpose algorithm
In [16], a general framework for deriving approximation algorithms is
provided. Following the scheme in [16] which was originally applied to
IIKP, we consider the following algorithm A. The algorithm employs an
ε–approximation scheme to obtain a feasible solution for each knapsack
problem KPt with solution value denoted by ztA for t = 1, . . . , T . Each
such solution is also a feasible solution for IKP where the items constituting ztA are present in all successive time periods (and no other items). The
algorithm chooses as a solution value z A the maximum among all these
candidates, i.e.
( T
)
X
z A = max
(5)
∆τ ztA .
t=1,...,T

τ =t

The obvious extension of A, which solves each knapsack problem KPt to
optimality with value zt (instead of ztA ) and then proceeds as in (5), will be
A∗
A∗ is not polynomial.
denoted by A∗ with solution values
PT z . ∆Clearly,
t
, with Θ ≤ T . The following
Let us define quantity Θ =
t=1 PT
τ =t

∆τ

generalization of Theorem 3 in [16] holds.

Theorem 2. Algorithm A is an approximation algorithm for IKP with ap1−ε
proximation ratio at least 1−ε
Θ ≥ T .
Proof. For each t = 1, . . . , T we have

∆t ztA
1−ε

≥ zt∗ and also ztA ≤

zA
T
P
∆τ

from

τ =t

(5). Then, the following series of inequalities holds:
∗

z =

T
X
t=1

zt∗

T
T
X
X
∆t ztA
≤
≤
(1 − ε)
t=1
t=1

Θ zA
∆t z A
zA
1−ε
=
=⇒
≥
T
P
1−ε
z∗
Θ
∆τ
(1 − ε)
τ =t

7

For IIKP considered in [16], we have Θ = HT with HT ≈ ln T being
the T -th harmonic number. At the present state of the art, the tightness of
this bounds is an open question even for IIKP. Considering the variant A∗ ,
where each KPt is solved to optimality (i.e. algorithm A for ε = 0), we can
state the following result.
Theorem 3. For any value of T and any choice of time multipliers ∆t ,
1
for IKP.
algorithm A∗ has a tight approximation ratio Θ
Proof. We can evaluate the performance of algorithm A∗ by an alternative
analysis based on a Linear Programming model. More precisely, we consider
an LP formulation with non-negative variables hA and ht associated with
∗
z A and zt respectively and a positive parameter OP T > 0 associated with
z ∗ . The corresponding LP model for evaluating the worst case performance
of algorithm A∗ is as follows:
minimize
subject to

hA

(6)

hA −
T
X
t=1
A

T
X
τ =t

∆τ ht ≥ 0

∆t ht ≥ OP T

h ≥0

ht ≥ 0

t = 1, . . . , T ;

(7)
(8)
(9)

t = 1, . . . , T.

(10)

The value of the objective function (6) provides a lower bound on the worst
case performance of algorithm A∗ . Constraints (7) guarantee that the contribution of each optimal knapsack solution KPt as a solution of IKP will be
taken into account according to (5). Constraint (8) indicates that the sum
of the knapsack solutions zt , multiplied by the associated ∆t , constitute a
trivial upper bound on z ∗ . Constraints (9), (10) indicate that variables are
non-negative. Solving model (6)–(10) to optimality provides lower bounds
hA
on the performance ratio of algorithm A∗ equal to OP
T for any T . We will
derive the optimal solutions of model (6)–(10) by considering the related
dual problem. Let us introduce T + 1 dual variables λi (i = 1, . . . , T + 1)
associated with constraints (7)–(8) respectively. The dual formulation of

8

model (6)–(10) is as follows:
maximize
subject to

OP T λ(T +1)

(11)

T
X

(12)

t=1

−

∆t ≤ 1

T
X
τ =t

λt ≥ 0

∆τ λt + ∆t λ(T +1) ≤ 0

t = 1, . . . , T ;

t = 1, . . . , T + 1.

(13)
(14)

Constraints (12)–(13) correspond to primal variables hA , ht (t = 1, . . . , T )
respectively. Feasible solutions of primal and dual models are:
hA =

OP T
OP T
; ht = T
Θ
P
∆τ Θ

t = 1, . . . , T ;

(15)

t = 1, . . . , T.

(16)

τ =t

λ(T +1)

∆t
1
= ; λt = T
Θ
P
∆τ Θ
τ =t

It is easy to verify that such solutions are feasible and satisfy all corresponding constraints to equality for any distribution of time multipliers and for
any value of T . Since hA = OP T λ(T +1) , by strong duality both primal and
A

1
h
dual solutions are also optimal. Hence, the bound OP
T is equal to Θ for
any T .
It was shown in Theorem 2 (for ε = 0 ) that the approximation ratio
of A∗ is at least Θ1 . Now we will derive instances where this bound can
be reached. Therefore, we construct instances where the optimal solution
values of KPt in each period t are equal to the values of ht for t = 1, . . . , T in
(15) and where the optimal solution value for IKP is equal to the weighted
T
P
sum of all these solutions, namely z ∗ =
∆t ht . Such target instances can
t=1

be generated by the following procedure:

A. We first represent quantity Θ as a fraction, i.e. Θ = ab where b is the
∆1
+
smallest common multiple of the denominators of fractions ∆1 +···+∆
T
∆T
· · · + ∆T . Then, we set OP T = a so as to get integer values ht .

9

B. We generate an IKP instance as follows:
n=

b
, pj = wj = 1 (j = 1, . . . , n), ct = ht (t = 1, . . . , T )
∆T

The optimal solution of each KPt will pack items until the corresponding
capacity ct is filled and thus will yield a solution value equal to ht . The
number of items is ∆bT because the capacity in the last period T is cT =
OP T
= ∆Ta a = ∆bT . At the same time, the optimal solution for
hT = ∆
TΘ
b
IKP can be obtained by progressively packing all items over time periods
T
T
P
P
while filling the capacities ct , hence z ∗ =
∆t ct =
∆t ht .
t=1

t=1

As an example of the outlined procedure, consider the IIKP variant
with T = 3 for which HT = 11
6 . Correspondingly, the following instance
with n = 6, pj = wj = 1 (j = 1, . . . , 6), c1 = 2, c2 = 3, c3 = 6 is generated.
The optimal solution is given by greedily packing as many items as possible
in each time period and thus filling the corresponding capacities (z ∗ = 11).
The optimal solutions values of the KPs are equal to 2, 3, 6 respectively.
∗
Hence we have z A = max{3 · 2, 2 · 3, 6} = 6 which proves the tightness of
6
the approximation bound H13 = 11
.
We remark that the bound tightness cannot be straightforwardly generalized to algorithm A, where an ε–approximation scheme is run for solving
each KP. We could get the ratio in Theorem 2 by solving model (6)–(10)
T
P
where the term
∆t ht in constraint (8) is divided by (1−ε) and the optimal
t=1

values of primal variables are multiplied by (1 − ε). However, the generation of tight instances is strictly related to the choice of the approximation
algorithm for KPs.
3.2. A PTAS when T is a constant

In the following it will be convenient to consider a residual problem IKPR
∗ . It is derived from any given instance of IKP
with optimal solution value zR
by defining a subset of items, a residual capacity cR
t ≤ ct for every time
R
R
period t with ct−1 ≤ ct , and an earliest insertion time tj , which means
that item j cannot be put into the knapsack in time periods before tj .
Formally, the conditions xjτ = 0 for τ < tj are added in the ILP model.
Obviously, every IKP instance is equivalent to a restricted instance IKPR
with tj := min{t | ct ≥ wj , t = 1, . . . , T }. Clearly, the solution value of the
10

LP-relaxation of this IKPR can be smaller than the LP-relaxation of IKP.
Concerning the structure of the LP-relaxation of IKPR we can observe the
following.
Lemma 4. The solution of the LP-relaxation of IKPR contains at most T
fractional items.
Proof. We claim that considering the time periods from t = 1, . . . , T at most
one additional fractional item can appear in any period t which implies the
above statement.
Assume that in some period t there are two new fractional items j1 and
j2 in the solution (which were not packed at all in periods before t) with
efficiencies pj1 /wj1 ≥ pj2 /wj2 . Similar to the standard KP (see [19, Theorem
2.2.1]) one can invoke an exchange argument and shift weight from j2 to j1
by setting d := min{wj2 xj2 t , wj1 (1 − xj1 t )} and defining a new solution with
x′j1 t := xj1 t + d/wj1 and x′j2 t := xj2 t − d/wj2 . Obviously, the total capacity
consumed by items j1 and j2 does not change in period t and neither in
any later periods up to T . Hence, the new solution is feasible and gives a
higher profit contribution in all periods t, t + 1, . . . , T . Moreover, in the new
solution at most one of j1 and j2 has a fractional value in period t.
Note that a fractional item introduced in some period t may well be
increased during a later period and possibly reach 1. Moreover, different
from the LP-relaxation for IKP, it may be the case that the capacity is not
fully utilized in some periods. This can occur e.g. in some period t, if a
highly efficient item with large weight has an earliest insertion time larger
than t. In this case it can make sense to leave some empty space in period
t and thus allow this item to be fully packed when it becomes available.
Taking a closer look at the solution structure of the LP-relaxation of
IKPR we can also compute it by a combinatorial algorithm with polynomial
running time. However, the details of this algorithm are beyond the scope
of this paper.
Computing the LP-relaxation of any restricted instance IKPR and round′ . It foling down all fractional values gives a feasible solution with value zR
lows from Lemma 4 that the maximum loss from rounding down is bounded
by T times the maximum profit contribution of a single item. Thus we have:
∗
zR

≤

′
zR

+ T · max

j=1,...,n

11

T
X

τ =tj

∆τ pj

(17)

For a residual problem IKPR we can apply the following approximation
algorithm A′ , which is a variant of algorithm A described in Section 3.1. We
A′ . Then
run an FPTAS for each time period t yielding ε-approximations ztR
we also consider an alternative solution derived by computing the optimal
solution of the LP-relaxation of IKPR and rounding down all fractional
′ . Finally, we
variables to 0 as described above reaching a solution value zR
take the maximum between these T +1 candidates obtaining a solution value
A′ , namely
zR
(
( T
))
X
A′
′
A′
zR = max zR , max
.
(18)
∆τ ztR
t=1,...,T

τ =t

With Theorem 2 the overall approximation ratio of algorithm A′ for IKPR
can be bounded by ρ = 1−ε
T . Note that the introduction of earliest insertion
times for items in IKPR does not interfere with the analysis in Theorem 2.
′ can be done in polynomial time poly(n, T ). The T execuComputing zR
tions of a FPTAS for KP can be bounded by O(T (n log( 1ε ) + ( 1ε )3 log2 ( 1ε ))),
see [18].

Similarly to the line of reasoning for deriving PTAS’s for KP (see, e.g.,
[22, 4]), we propose an approximation scheme for IKP. It is based on guessing (by going through all possible choices) the set Sk of k items and the associated starting periods stj for each item j ∈ Sk which give the largest profit
contributions in an optimal solution. For convenience, the minimum
profit
P
contribution of an item in Sk is denoted by pcm = minj∈Sk { Tτ=stj ∆τ pj }.
For each such choice of Sk and starting periods, if it is feasible, one
R
can define the following
Presidual instance IKP . It consists of the residual
R
capacities ct = ct − j∈Sk ,stj ≤t wj in each time period t. To preserve
R R
the incremental capacity structure of IKP we set cR
t := min{ct , ct+1 } for
t = T − 1, T − 2, . . . , 1, which is without loss of generality because of (3).
The item set of IKPR is restricted to items not in Sk with profit contribution
not exceeding pcm, which can be enforced by setting the earliest insertion
time tj for all items j 6∈ Sk as
(

tj = min t | cR
t ≥ wj ,

T
X
τ =t

∆τ pj ≤ pcm, t = 1, . . . , T

)

.

If the minimum is taken over the empty set, we remove j from IKPR . We
can now state our approximation scheme, denoted by algorithm Approx.

12

Algorithm Approx
Input: IKP instance,
n l moε.
1: Set k := min n, Tε
.
2: Generate all subsets of {1, . . . , n} consisting of less than k items.
For each such subset generate all possible starting periods of items and
check the feasibility for IKP.
Let z ε be the best objective value over all generated feasible solutions.
3: For each subset Sk ⊆ {1, . . . , n} with |Sk | = k, generate all possible
starting periods of items and check the feasibility for IKP.
4: For every resulting feasible configuration, compute the overall profit
P
contribution P C(k) = j∈Sk pcj and the minimum contribution pcm.
Determine the corresponding residual IKP instance IKPR .
A′ .
Apply algorithm A′ to IKPR yielding a solution value zR
A′ + P C(k)}
Update z ε := max{z ε , zR
The following proposition characterizes the running time of Approx.
Proposition 5. The running time complexity of Approx is polynomial in
the size n of the input.
Proof. The running time mainly depends on the number of configurations
generated in Step 3. There are O(nk ) subsets Sk and for each item T possible
starting periods, i.e. O(T k ) possible choices for each Sk . For each such
configuration algorithm A′ is performed in Step 4. This dominates the effort
spent in Step 2. Plugging in the definition of k the overall complexity is:




1 3
1
2 1
⌈ Tε ⌉ ⌈ Tε ⌉
(19)
· poly(n, T ) + T n log( ) + ( ) log ( )
O n T
ε
ε
ε
The following theorem describes the approximation ratio reached by Approx.
Theorem 6. Algorithm Approx is a PTAS for IKP when T is a constant.
Proof. We will show in this proof that the algorithm is an ε–approximation
scheme. Then, it follows from the time complexity stated in Proposition 5
that Approx is a PTAS for IKP when T is a constant.
13

l m
If k = n, namely n ≤ Tε , Steps 2 or 3 of Approx would even compute
an optimal solution since all subsets of the n items are enumerated, and
therefore the
l mstatement is trivial. Thus, it remains to consider the case
where k = Tε .
We consider two cases depending on a parameter f ∈ (0, 1) and analyze
the iteration of Step 3 where Sk and the associated starting periods stj yield
the largest profit contribution P C(k) of any subset of k items in the optimal
∗ and by
solution. In the corresponding execution of Step 4 we denote by zR
R
pmax the optimal solution value and the maximum profit of the items in the
respective residual instance R.
Case 1: P C(k) ≥ f · z ∗ .
Since the k items with maximal profit contribution in the optimal solution
∗ + P C(k). Using the approximation ratio ρ
are considered, we have z ∗ = zR
′
of A , the following series of inequalities holds:
′

A
∗
z ε ≥ P C(k) + zR
≥ P C(k) + ρ zR

= P C(k) + ρ(z ∗ − P C(k)) = (1 − ρ)P C(k) + ρz ∗
∗

∗

≥ (1 − ρ)f z + ρz = ((1 − ρ)f + ρ) z

(20)

∗

Case 2: P C(k) < f · z ∗ .
Since the profit contribution of any item in IKPR is bounded by pcm, we
also for any item j in IKPR
pcj ≤ pcm ≤

1
1
P C(k) < f z ∗ .
k
k

(21)

Then, the following series of inequality holds:
∗
z ∗ = P C(k) + zR

≤ P C(k) +

A′
zR

(22)
+ T · max pcj
j6∈Sk

1
A′
≤ P C(k) + zR
+ T · f z∗
k
1 ∗
ε
≤ z +T fz
k

(23)
(24)
(25)

The first inequality comes from (17), the second inequality from (21). Now
(22)-(25) is equivalent to
1
z ε ≥ (1 − T f ) z ∗ .
k
14

(26)

Given ε and ρ, we now set f as follows:
f := 1 −

ε
1−ρ−ε
=
1−ρ
1−ρ

We easily note that f < 1 and we also have f > 0 since ρ =
1 − ε > ρ. For Case 1, plugging the value of f in (20) yields
z ε ≥ ((1 − ρ)f + ρ) z ∗

= ((1 − ρ − ε) + ρ) z ∗ = (1 − ε) z ∗ .

For Case 2, we plug in k =

l m
T
ε

(27)
1−ε
T

and thus

(28)

into (26) and get

z ε ≥ (1 − εf ) z ∗ ≥ (1 − ε) z ∗ .

(29)

We remark that in [2] a√ PTAS is introduced under the more general
assumption that T is in O( log n), but only for IIKP. For constant T , it
can be extended to decreasing time multipliers ∆t . Furthermore, in [12] a
PTAS is given for IIKP for arbitrary T and for IKP with increasing time
multipliers. All these PTASs rely on solving a huge number of non–trivial
LP models. Our approach works for general multipliers ∆t and does not
require the solution of LP models.
4. Approximation algorithms for a weight constrained IKP variant
There are two essential decisions in IKP, namely whether to select an
item at all, and – if yes – when to select it. Thus, it seems natural not to
restrict the latter decision to a subset of time periods and allow each item to
be selected at any point in time, also in period 1. Therefore, in the reminder
of the paper we will consider IKP under the mild and natural assumption
that each item can be packed in the first period, i.e. wi ≤ c1 , i = 1, . . . , n.
We refer to this weight constrained variant of the problem as IKP′ and to
the related version with unit time multipliers ∆t = 1 for all t as IIKP′ .
Let us denote by st the split items in the linear relaxation of each KPt
for t = 1, . . . , T , which also correspond to the fractional items in the optimal solution of IKP′LP . We state the following algorithm H1 , which is
independent from the given multipliers ∆t .

15

Algorithm H1
Input: IKP′ instance.
p
1: Sort items by decreasing wi (i = 1, . . . , n) and solve IKP′LP .
Ps1 i
2: Let t̂ = min{t | ct ≥
j=1 woj , t = 1, . . . , T }.
nP
s1 −1
Let p = max
j=1 pj , ps1 .

Pack the item(s) yielding profit p in time periods 1 to t̂ − 1.
Pack all items j = 1, . . . , s1 in time periods t̂ to T .
4: Add the remaining items of the optimal solution of IKP′LP ignoring all
fractional values.
3:

The following theorem holds.
Theorem 7. Algorithm H1 has a tight 21 -approximation ratio for IKP′ for
any choice of multipliers ∆t .
Proof. Consider the optimal profit values zt of KPt for t = 1, . . . , T (without
multipliers). From the properties of KP and since items are ordered by
decreasing wpii , we have:
max


t −1
sX


pj , ps t



j=1

Pst −1
j=1

Pst −1
j=1




pj
wj

≥

1
zt
2

ps t
wst

≥

t = 1, . . . , T

t = 1, . . . , T

(31)

Algorithm H1 yields a solution with value


sX
t̂−1
T
t −1
1 −1
 X
sX
X
H1
pj .
z =
∆t · max
∆t ·
pj , ps 1 +


t=1

j=1

t=t̂

(30)

(32)

j=1

P t −1
P1
Since inequalities sj=1
wj ≥ sj=1
wj > c1 ≥ wi hold for any item i and
Pst −1
t ≥ t̂, from (31) we get j=1 pj > pst for any t ≥ t̂ and thus
max


t −1
sX


j=1

pj , ps t





=

sX
t −1
j=1

16

pj

t = t̂, . . . , T.

(33)

Considering (30), (32), (33) and that
we get

PT

t=1 ∆t zt

t̂−1

z H1 ≥

is an upper bound on z ∗ ,

T

1X
1X
1
∆t zt +
∆t zt ≥ z ∗
2 t=1
2
2

(34)

t=t̂

which shows that algorithm H1 has an approximation ratio of 12 .
To prove the tightness of the bound, consider the following instance with
ct = M + t for t = 1, . . . , T (with integer M ≫ T ) and 3 items with entries
p1 =

M
M
M
M
M
M
+δ, w1 =
; p2 =
+T +1, w2 =
+T +1; p3 =
−δ, w3 =
;
2
2
2
2
2
2

with δ > 0 being an arbitrary small number. Algorithm H1 will select
only
item over all time periods getting a solution with value
PT the second
′
M
t=1 ∆t ( 2 + T + 1). The optimal IKP solution will pack items 1 and 3
for all periods independently from the multipliers ∆t reaching a value of
P
T
t=1 ∆t · M . Hence, the approximation ratio of the algorithm is
PT

M
t=1 ∆t ( 2 + T
PT
t=1 ∆t M

+ 1)

which reaches a value arbitrarily close to
trary multipliers ∆t .

=
1
2

1 T +1
+
2
M

for large values of M and arbi-

Given the approximation ratio of this simple heuristic, it is worth to investigate to what extent computationally more involved iterative approaches
could improve upon the worst case performance of algorithm H1 . We consider an algorithm, denoted as H2 , which also considers the periods from
t = 1 to T but computes in each step an optimal knapsack solution instead
of the rounded down LP-relaxation.

17

Algorithm H2
Input: IKP′ instance.
1: Solve KP1 to optimality and pack Sol(KP1 ) in all periods 1, . . . , T .
2: For all periods t = 2, . . . , T :
Solve to optimality the knapsack problem induced by KPt with the
condition that all items packed in previous periods remain packed in
period t.
Pack the additional item set in period t.
Contrary to our expectation, we can show the following negative result
for algorithm H2 . It turns out quite surprisingly that algorithm H2 , which
locally dominates H1 for each period, yields a worse performance ratio for
the overall problem for almost
P any choice of multipliers. Only for extremely
large ∆1 , namely if ∆1 > Tt=3 ∆t (t − 2), H2 outperforms H1 from a worst
case perspective.
Theorem 8. Algorithm H2 has a tight approximation ratio of
for IKP′ .
Note that for IIKP′ we get a ratio of

PT
∆t
PTt=1
∆
t=1 t t

≥

1
T

2
T +1 .

Proof. We first show the lower bound on the performance ratio of H2 . For
every period t = 1, . . . , T we denote by πt∗ (resp. πt ) the total profit of the
items added in period t in the optimal solution of IKP′ (resp. added by
the optimal solution of the residual knapsack problem solved in H2 ). Note
that π1 is the optimal solution value of KP1 . For every period t denote by
Ot all items selected in period t in the optimal ILP solution and by It all
items packed by H2 (independently from their starting period and without
accounting for the multiplier
values contributed in
P ∆t ). The total profit
P
period t are thus p(Ot ) = tj=1 πj∗ and p(It ) = tj=1 πj respectively.
Now we compare the optimal solution with the outcome generated by
H2 . By construction there is π1∗ ≤ π1 . We will prove the crucial claim that
in each successive time period an additional profit deviation of at most pmax
can be accrued, namely:
πt∗ − πt ≤ pmax

t = 2, . . . , T

(35)

For any period t ≤ T − 1, we partition the items added in period t + 1 and
∗
contributing to the optimal profit value πt+1
into a set I h , which are items
also in It , and a set I n consisting of items not yet packed by H2 .
18

We now estimate the value of πt+1 by constructing an auxiliary set I ′
as follows. Let I p := Ot \ It . All items in Ot+1 \ It = I p ∪ I n are clearly
available for πt+1 (possibly among many others).
We fill items into I ′ and stop as soon as w(I ′ ) > ct+1 − ct . This is done
by first considering the items in I n and then items in I p , both in arbitrary
order.
In the unusual case that we do not reach the stopping criterion we would
have w(I ′ ) = w(I n ) + w(I p ) ≤ ct+1 − ct and thus πt+1 ≥ p(I ′ ). But then we
have Ot+1 = I ′ ∪ It and thus even p(It+1 ) ≥ p(Ot+1 ).
Otherwise, after removing again the item added most recently into I ′ , we
have a solution at hand which can be packed by H2 since its weight is at
most ct+1 − ct . We will prove the following inequality
∗
p(I ′ ) ≥ πt+1
.

(36)

From (36) our original claim (35) follows because removing an item from I ′
gives a lower bound for πt+1 and thus we would have πt+1 ≥ p(I ′ ) − pmax ≥
∗
πt+1
− pmax .
To prove (36), we first show that I ′ contains all items of I n . Assume
otherwise that some item i ∈ I n is not in I ′ . Then we have
ct+1 ≥ w(Ot ) + w(I n ) ≥ w(Ot ) + w(I ′ ) + wi > w(Ot ) + ct+1 − ct + wi ,
which means that w(Ot ) + wi < ct and thus item i could have been added
already to Ot in contradiction to optimality.
Next we show that w(I h ) cannot be too large. Denote as I ′′ := I ′ ∩I p , i.e.
the items added to I ′ which were already included in Ot . Clearly I ′ = I ′′ ∪I n .
If w(I h ) ≥ ct − w(Ot \ I ′′ ) then we have:
w(Ot+1 ) = w(Ot \ I ′′ ) + w(I ′′ ) + w(I h ) + w(I n )
′′

h

′′

h

′

= w(Ot \ I ) + w(I ) + w(I )

> w(Ot \ I ) + w(I ) + ct+1 − ct
′′

′′

≥ w(Ot \ I ) + ct − w(Ot \ I ) + ct+1 − ct = ct+1

(37)
(38)
(39)
(40)

which is a contradiction. Hence, we must have that w(I h ) < ct − w(Ot \ I ′′ ).
Therefore, I h could be used in Ot instead of I ′′ . The fact that this was not
done by the optimal solution implies that p(I h ) ≤ p(I ′′ ) which is equivalent
∗
= p(I h ) + p(I n ) ≤ p(I ′′ ) + p(I n ) = p(I ′ ) and (36) is shown.
to πt+1

19

Thus, considering (35), for any period t ≥ 2 we have
π1∗ +

t
X
(πj∗ − πj ) ≤ π1 + (t − 1)pmax =⇒ p(Ot ) ≤ p(It ) + (t − 1)pmax (41)
j=2

Summing up (41) over all periods we get
z∗ =
≤

T
X

t=1
T
X
t=1

∆t p(Ot )

(42)

∆t (p(It ) + (t − 1)pmax )

(43)

= z H2 + pmax

T
X
t=1

≤ z

H2

z H2

+ PT

t=1 ∆t

∆t (t − 1)
·

T
X
t=1

(44)

∆t (t − 1) = z

H2

PT

· Pt=1
T

∆t t

t=1 ∆t

(45)

which shows the stated approximation ratio. The last inequality
PT (45) derives
H
2
from the trivial fact that π1 ≥ pmax and thus z ≥ pmax t=1 ∆t .
The minimum of this bound is reached for multipliers ∆1 = . . . =
∆T −1 = ε for small ε > 0 and ∆T = 1 where the approximation ratio
tends to T1 .
We can prove the tightness of the bound for arbitrary multipliers ∆t by
considering the following instance with capacities ct = t · M + (T − t) and
2 T items with entries
w1 = p1 = M + (T − 1),

w2 = w3 = · · · = wT

p2 = p3 = · · · = pT

wT +1 = wT +2 = · · · = w2T

pT +1 = pT +2 = · · · = p2T

= M − 1,
= 1,

= M,
= M.

Note that ct+1 − ct = M − 1. The solution provided by algorithm H2 starts
with KP1 and packs item 1. For KP2 the residual capacity is c2 −c1 = M −1,
so only item 2 with profit 1 can be packed. This argument continues for each

20

KPt . Hence, we have as solution value
z H2 =

T
X
t=1

∆t · (M + (T − 1)) +

T
X
t=2

∆t (t − 1).

The optimal IKP′ solution packs t copies of items with weight and profit M
in each time period t which yields
∗

z =

T
X
t=1

∆t t · M.

This shows the tightness of the approximation bound for large M .
Mirroring the iterative strategy of algorithm H2 , one may consider another natural heuristic approach which starts from the optimal solution of
the last knapsack problem KPT and moves upwards until period 1 by solving
to optimality the knapsack problem induced by KPt (t = T − 1, . . . , 1) with
item set restricted to those items packed in period t + 1. Still, it turns out
that this strategy cannot improve the approximation ratio of the polynomial
time heuristic H1 . We show this observation by giving a class of instances
where the above algorithm reaches only z ∗ /3. Consider the following IIKP′
instance with capacities ct = 4 − γ, (t = 1, . . . , T − 2), c(T −1) = 4 + γ, cT = 5
(with γ > 0 being an arbitrary small number) and four items with entries:
j
pj
wj

1
1+γ
2

2
1+γ
2

3
1
1

4
2
3−γ

The sketched alternative approach will select items 1, 2, 3 in the last
period T , items 1 and 2 in period T − 1 and either item 1 or item 2 in the
remaining periods. The corresponding profit is equal to
(3 + 2γ) + (2 + 2γ) + (1 + γ)(T − 2) = (1 + γ)T + 3 + 2γ.
The optimal solution instead consists in packing items 3 and 4 in all periods,
hence z ∗ = 3T . Consequently, the approximation ratio of the algorithm is
strictly less than 12 for large enough T and cannot be greater than 13 as the
number of periods T increases.

21

5. An approximation algorithm for a weight constrained IKP variant with two periods
In this section we consider IKP′ for the special cases with two periods
only, namely T = 2. It turns out that a more careful analysis of the solution
structures of the knapsack subproblems KPt by means of an LP model gives
much better approximation ratios than the more general results presented
in Section 4. Let us define for the optimal solution sets Sol(KP1 ) and
Sol(KP2 ) the following subsets illustrated in Figure 1:
• S12 : subset of items included in both optimal solutions Sol(KP1 ) and
Sol(KP2 );
• S1 : remaining subset of items in Sol(KP1 );
• S2a : remaining subset of items not exceeding capacity c1 in Sol(KP2 );
• S2′ : first item exceeding c1 in Sol(KP2 );
• S2b : remaining subset of items in Sol(KP2 );
Each subset could as well be empty. The dashed lines in Figure 1 refer to
the item S2′ which exceeds the first capacity value.
c1
KP1 :

S12

KP2 :

S12

S1
c2
S2a

S2′

S2b

Figure 1: Decomposition of the optimal solutions of KP1 and KP2 .

According to the above definitions, we have the following inequalities:
w(S12 ) + w(S1 ) ≤ c1

w(S12 ) +
w(S12 ) +
w(S12 ) +
w(S12 ) +

w(S2a )
w(S2a )
w(S2a )

(46)

≤ c1

+ w(S2′ ) > c1
+ w(S2′ ) + w(S2b )
w(S1 ) + w(S2b ) < c2

(47)
(48)
≤ c2

(49)
(50)

Inequality (50) derives directly from inequalities (46), (48) and (49). The
optimal solution values of KP1 and KP2 are z1 = p(S12 ) + p(S1 ) and z2 =
p(S12 ) + p(S2a ) + p(S2′ ) + p(S2b ) respectively. Now we can state three feasible
solutions for IKP′ :
22

a) Sol(KP1 ) in the two periods plus the additional packing of items in S2b
in the second period with total profit
∆1 (p(S12 ) + p(S1 )) + ∆2 (p(S12 ) + p(S1 ) + p(S2b ));
b) Sol(KP2 ) in the second period with the packing of items in subsets S12
and S2a in the first period and resulting profit
∆1 (p(S12 ) + p(S2a )) + ∆2 (p(S12 ) + p(S2a ) + p(S2′ ) + p(S2b ));
c) Sol(KP2 ) in the second period with item S2′ placed in the knapsack in
the first period. The profit of this solution is
∆1 p(S2′ ) + ∆2 (p(S12 ) + p(S2a ) + p(S2′ ) + p(S2b )).
We introduce an algorithm, hereafter denoted as HT 2 , which simply returns
the best of these solutions.
Algorithm HT 2
Input: IKP′ instance with T = 2.
1: Compute Sol(KP1 ) and Sol(KP2 ).
2: Identify subsets S12 , S1 , S2a , S2′ , S2b and compute solutions a), b), c).
3: Return the best solution found.
Theorem 9. For IKP′ with T = 2, algorithm HT 2 has a tight approximation
2
∆2
r +2∆r
ratio of 1+3∆
1+4∆r +2∆2 , where ∆r = ∆1 .
r

Proof. In order to evaluate the worst case performance of algorithm HT 2 ,
we consider an LP formulation where we associate a non–negative variable h
with the solution value computed by the algorithm. In addition, the profits
of the subsets p(S(·) ) are associated with non–negative variables s(·) . As in
Section 3.1, the positive parameter OP T represents z ∗ . This implies the

23

following parametric LP model with ∆1 and ∆2 :
minimize
subject to

h

(51)

h − ((∆1 + ∆2 )(s12 + s1 ) + ∆2 sb2 ) ≥ 0
h − ((∆1 + ∆2 )(s12 + sa2 ) + ∆2 (s′2 + sb2 )) ≥ 0
h − ((∆1 + ∆2 )s′2 + ∆2 (s12 + sa2 + sb2 )) ≥ 0
∆1 (s12 + s1 ) + ∆2 (s12 + sa2 + s′2 + sb2 ) ≥ OP T
h, s12 , s1 , sa2 , s′2 , sb2 ≥ 0

(52)
(53)
(54)
(55)
(56)

The objective function value (51) represents a lower bound on the worst case
performance of algorithm HT 2 . Constraints (52)–(54) guarantee that HT 2
will select the best of the three feasible solutions. Constraint (55) states that
the sum ∆1 z1 + ∆2 z2 constitutes an upper bound on z ∗ . Constraints (56)
indicate that the variables are non-negative. A feasible solution of model
(51)–(56), for any ∆1 > 0 and ∆2 > 0, is:
(1 + 3∆r + 2∆2r )OP T
∆r OP T
, s1 =
2
1 + 4∆r + 2∆r
∆1 (1 + 4∆r + 2∆2r )
(1 + ∆r )OP T
, sa = sb2 = 0.
= s′2 =
∆1 (1 + 4∆r + 2∆2r ) 2

h=
s12

We will show by strong duality that such a solution is also optimal for
any positive value of ∆1 and ∆2 . If we denote by λi with i = 1, . . . , 4
the dual variables related to constraints (52)–(55), the dual linear problem
corresponding to model (51)–(56) is as follows:
maximize
subject to

OP T · λ4

(57)

λ1 + λ2 + λ3 ≤ 1

(58)

− ∆2 λ3 − (∆1 + ∆2 )(λ1 + λ2 − λ4 ) ≤ 0

(60)

∆2 (λ4 − λ2 ) − (∆1 + ∆2 )λ3 ≤ 0

(62)

∆1 λ4 − (∆1 + ∆2 )λ1 ≤ 0

∆2 (λ4 − λ3 ) − (∆1 + ∆2 )λ2 ≤ 0
− ∆2 (λ1 + λ2 + λ3 − λ4 ) ≤ 0

λ1 , λ2 , λ3 , λ4 ≥ 0

(59)
(61)
(63)
(64)

Constraints (58)–(63) correspond to primal variables h, s1 , s12 , sa2 , s′2 , sb2 re-

24

spectively. A feasible dual solution (for any ∆1 > 0 and ∆2 > 0) reads
λ1 =

1 + 2∆r
(1 + ∆r )∆r
1 + 3∆r + 2∆2r
,
λ
=
λ
=
,
λ
=
.
2
3
4
1 + 4∆r + 2∆2r
1 + 4∆r + 2∆2r
1 + 4∆r + 2∆2r

Hence, the dual solution value OP T ·λ4 = h proves by strong duality the optimality of the primal solution for any value of the two time multipliers. The
corresponding lower bound on the performance ratio provided by algorithm
1+3∆r +2∆2r
HT 2 is equal to OPh T = 1+4∆
2.
r +2∆
r

We can show the tightness of the bound by considering two different
instances for ∆r ≤ 1 and ∆r > 1 respectively, with n = 5, c1 = 3 + γ, c2 = 4
and following entries:

∆r ≤ 1
∆r > 1

i
pi
wi
pi
wi

1

2

3

4

5

1+∆r
∆1

1+∆r
∆1

∆r
∆1

1+2∆r −γ
∆1

1
∆1

3 − 2γ

1 + 2γ

∆r −γ
∆1

1
∆1

1

1

2

2

1+γ

1+2∆r
∆1

1+∆r
∆1

1+∆r
∆1

3+γ

2

2

First, consider the instance for the case ∆r ≤ 1. The optimal solutions
of KP1 and KP2 consist of items 1, 3 and items 1, 2 respectively. Correspondingly, we have
S12 = {1}, S1 = {3}, S2a = {∅}, S2′ = {2}, S2b = {∅}.
An easy computation reveals that all the solutions provided by algorithm
HT 2 have the same profit value of 1 + 3∆r + 2∆2r . The optimal IKP′ solution
selects item 4 in the first period together with item 5 in the second one, hence
z ∗ = 1 + 4∆r + 2∆2r − (1 + ∆r )γ.
In the second instance with ∆r > 1, we have Sol(KP1 ) = {1}, Sol(KP2 ) =
{2, 3} and thus
S12 = {∅}, S1 = {1}, S2a = {2}, S2′ = {3}, S2b = {∅}.
Also in this case all solutions provided by the algorithm have a profit equal
to 1+3∆r +2∆2r . An optimal solution packs items 2 and 4 in the first period
together with item 5 in the second one, hence z ∗ = 1+4∆r +2∆2r −(1+∆r )γ.
In both cases, the approximation ratio of algorithm HT 2 can be arbitrarily
2
r +2∆r
as the value of γ goes to 0.
close to ratio 1+3∆
1+4∆r +2∆2
r

25

Corollary√ 10. The approximation
ratio of algorithm HT 2 is bounded from
√
2
′
6
1
+
.
When
H
below by 22√2+3
=
T 2 is applied to IIKP , the ratio is 7 .
2
4
2+4
Proof. A straightforward computation reveals that function
a unique global minimum (for ∆r > 0) at ∆r =
ratio

h
OP T

is bounded from below by

Correspondingly,

1+3∆r +2∆2r
1+4∆r +2∆2r

√
2√2+3
.
2 2+4

√

2
2 .

1+3∆r +2∆2r
1+4∆r +2∆2r

has

Hence, we get that the

For IIKP′ , we have ∆r = 1.

= 67 .

Considering algorithm HT 2 the following improvement comes to mind:
Solve to optimality KP2 after packing the item set Sol(KP1 ) in both periods
(as in H2 ) and, as an alternative, optimally solve KP1 restricted to the item
set Sol(KP2 ). However, the above tight instance would also apply to this
computationally more demanding variation and thus no improvement of the
approximation ratio can be gained.
Algorithm HT 2 is not a polynomial time algorithm since it requires the
optimal solutions of KP1 and KP2 . We could solve these knapsack problems
by an ε–approximation scheme (FPTAS) to get a polynomial running time
at the cost of a decrease of the approximation ratio. The following corollary
shows that the ratio is decreased by a factor (1 − ε).
Corollary 11. If an ε–approximation scheme is employed for solving the
standard knapsack problems KP1 and KP2 , the approximation ratio of al2
r +2∆r
gorithm HT 2 is at least 1+3∆
1+4∆r +2∆2 (1 − ε).
r

Proof. We consider again model (51)–(56) to evaluate the performance of the
algorithm. If the subsets S(·) correspond to the items of the ε–approximations
for KP1 and KP2 , constraints (52)–(54) straightforwardly hold. Then, we
just replace constraint (55) by constraint
∆1 (s12 + s1 ) + ∆2 (s12 + sa2 + s′2 + sb2 ) ≥ OP T (1 − ε)

(65)

which indicates that the weighted sum of the approximate solutions divided
by (1 − ε) provides an upper bound on the optimal solution value of IKP. In
the related primal/dual LP models, the optimal values of primal variables
are now multiplied by (1 − ε) while the optimal dual solution remains the
same with objective value (1 − ε)OP T · λ4 . The corresponding value of the
ratio OPh T shows the bound.

26

6. Conclusions
We proposed for IKP a series of results extending in different directions
the contributions currently available in the literature. We proved the tightness of the approximation ratio of a general purpose algorithm presented
in [16] and originally applied to the time-invariant version of the problem.
We also established a polynomial time approximation scheme (PTAS) when
one of the problem inputs can be considered as a constant. We then focused on a restricted relevant variant of IKP which plausibly assumes the
possible packing of any item since the first period. We discussed the performance of different approximation algorithms for the general case as well as
for the variation with two time periods. In future research, we will investigate extensions of our procedures to the design of improving approximation
algorithms for variants involving more than two periods. Also, since to the
authors’ knowledge no computational experience has been provided for IKP
so far, it would also be interesting to derive new solution approaches and
test their performance after generating benchmarks and challenging to solve
instances.
Acknowledgments
Ulrich Pferschy was supported by the project “Choice-Selection-Decision”
and by the COLIBRI Initiative of the University of Graz.
References
[1] Abolhassani, M., Chan, T. H., Chen, F., Esfandiari, H., Hajiaghayi,
M., Hamid, M., Wu, X., 2016. Beating Ratio 0.5 for Weighted Oblivious
Matching Problems. In: Sankowski, P., Zaroliagis, C. (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016). Vol. 57. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 3:1–3:18.
[2] Bienstock, D., Sethuraman, J., Ye, C., 2013. Approximation algorithms
for the incremental knapsack problem via disjunctive programming.
Available in: arXiv:1311.4563.
[3] Caprara, A., Furini, F., Malaguti, E., Traversi, E., 2016. Solving the
temporal knapsack problem via recursive Dantzig-Wolfe reformulation.
Information Processing Letters 116, 379–386.
[4] Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D., 2000. Approximation algorithms for knapsack problems with cardinality constraints.
European Journal of Operational Research 123, 333–345.
27

[5] Chimani, M., Wiedera, T., 2016. An ILP-based Proof System for the
Crossing Number Problem. In: Sankowski, P., Zaroliagis, C. (Eds.),
24th Annual European Symposium on Algorithms (ESA 2016). Vol. 57.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 29:1–29:13.
[6] Della Croce, F., Pferschy, U., Scatamacchia, R., (forthcoming). Approximation results for the incremental knapsack problem. In: 28th
International Workshop on Combinatorial Algorithms (IWOCA 2017).
[7] Della Croce, F., Pferschy, U., Scatamacchia, R., (forthcoming). New exact approaches and approximation results for
the penalized knapsack problem. Discrete Applied Mathematics. doi:10.1016/j.dam.2017.11.023.
[8] Della Croce, F., Salassa, F., Scatamacchia, R., 2017. An exact approach
for the 0–1 knapsack problem with setups. Computers & Operations
Research 80, 61–67.
[9] Della Croce, F., Salassa, F., Scatamacchia, R., 2017. A new exact approach for the 0–1 collapsing knapsack problem. European Journal of
Operational Research 260, 56–69.
[10] Dudziński, K., Walukiewicz, S., 1985. On the multiperiod binary knapsack problem. Methods of Operations Research 49, 223–232.
[11] Faaland, B., 1981. The multiperiod knapsack problem. Operations Research 29, 612–616.
[12] Faenza, Y., Malinović, I., 2017. Improved approximation algorithms
and disjunctive relaxations for knapsack problems. Available in:
arXiv:1701.07299.
[13] Furini, F., Monaci, M., Traversi, E., 2018. Exact approaches for the
knapsack problem with setups. Computers & Operations Research 90,
208–220.
[14] Giudici, A., Halffmann, P., Ruzika, S., Thielen, C., 2017. Approximation schemes for the parametric knapsack problem. Information Processing Letters 120, 11–15.
[15] Hartline, J., 2008. Incremental optimization. Ph.D. thesis, Cornell University.

28

[16] Hartline, J., Sharp, A., 2006. An incremental model for combinatorial
maximization problems. In: Àlvarez, C., Serna, M. J. (Eds.), WEA,
volume 4007 of Lecture Notes in Computer Science. Springer, pp. 36–
48.
[17] He, Y., Wang, X., He, Y., Zhao, S., Li, W., 2016. Exact and approximate algorithms for discounted 0-1 knapsack problem. Information Sciences 369, 634–647.
[18] Kellerer, H., Pferschy, U., 2004. Improved dynamic programming in
connection with an FPTAS for the knapsack problem. Journal of Combinatorial Optimization 8, 5–11.
[19] Kellerer, H., Pferschy, U., Pisinger, D., 2004. Knapsack Problems.
Springer.
[20] Martello, S., Toth, P., 1990. Knapsack problems: algorithms and computer implementations. Wiley.
[21] Pferschy, U., Scatamacchia, R., 2018. Improved dynamic programming
and approximation results for the knapsack problem with setups. International Transactions in Operational Research 25, 667–682.
[22] Sahni, S., 1975. Approximate algorithms for the 0–1 knapsack problem.
Journal of the ACM 22, 115–124.
[23] Sharp, A., 2007. Incremental algorithms: Solving problems in a changing world. Ph.D. thesis, Cornell University.
[24] Thielen, C., Tiedemann, M., Westphal, S., 2016. The online knapsack
problem with incremental capacity. Mathematical Methods of Operations Research 83, 207–242.

29

