# Polynomial Time Instances for the IKHO Problem

Authors: Romeo Rizzi; Luca Nardin
Journal: ISRN Electronics
 (2012)

---

## Abstract

The Interactive Knapsacks Heuristic Optimization (IKHO) problem is a particular knapsacks model in which, given an array of knapsacks, every insertion in a knapsack affects also the other knapsacks, in terms of weight and profit. The IKHO model was introduced by Isto Aho to model instances of the load clipping problem. The IKHO problem is known to be APX-hard and, motivated by this negative fact, Aho exhibited a few classes of polynomial instances for the IKHO problem. These instances were obtained by limiting the ranges of two structural parameters,c and u, which describe the extent to which an insertion in a knapsack in uences the nearby knapsacks. We identify a new and broad class of instances allowing for a polynomial time algorithm. More precisely, we show that the restriction of IKHO to instances where (c+2u)/c is bounded by a constant can be solved in polynomial time, using dynamic programming.


---

## Body

## 1. Introduction

Interactive Knapsacks Heuristic Optimization problem (IKHO) is a particular knapsacks model in which, given an array of knapsacks, an insertion in a knapsack influences the nearest knapsacks, in terms both of weight and of profit. It was introduced by Aho in [1], for solving the load clipping problem arising in electricity management application. It belongs to the general framework of the Interactive Knapsacks problems (IK) (also defined in [1]) which has several other applications, for example, in electricity management, single and multiprocessor scheduling, and packing of n-dimensional items to different knapsacks. Since IKHO is NP-complete [1] and APX-hard [2], the research of polynomial time instances is very important. In [3], Aho introduces a few classes of such instances restricting the values of certain parameters of the problem: c and u, which determine the dimension of the influence on other knapsacks caused by an insertion, and K, that limits the number of insertions. We keep on this line of investigation by adding a wide and significant class of polynomial time instances for the IKHO problem in the case when (c+2u)/c is bounded.Intuitively, in IKHO, when we insert an item in a knapsack, this item is replicated (cloned) to the c next knapsacks (hence forming a cloning block over c+1 consecutive knapsacks), and it causes an arbitrary but predetermined modification (radiation) of the weight and profit of the knapsacks at distance at most u from the cloning block (on both sides of the cloning block). After a knapsack is involved in a cloning operation, we are not allowed to insert any other item in that knapsack. Therefore, the cloning blocks are disjoint. In this paper, we are mainly interested in the case where the ratio between the whole width c+2u of the influenced zone (cloning plus radiation zones) and the width c of the cloning part is bounded by a constant r. We propose a dynamic programming algorithm based on a matrix of size O(cr×K), and having time complexity of O(cr×m×K), where m is the number of knapsacks and K represents the maximum number of cloning block that we can insert in the knapsacks array.In Section2, we give the original formulation of the problem from [1] and we then simplify it to ease our exposition in later sections. In Section 3, we give the algorithm. In Section 4, we sharpen the complexity result. Finally, in Section 5, we design a memory saving version of that algorithm.We conclude this section by defining some useful notation. Henceforth, we write0m to denote a zero constant vector of length m, that is, 0im=0 for i=1,…,m. Moreover, if x,y∈{0,1}m, we write x·y to indicate the concatenation of the two binary strings. Furthermore, [a,b] always denotes a range of integers and, if a>b, we assume that [a,b] is empty. In the same way, if a>b, the notation fori=a,…,b means for noi.


## 2. Formulation of the IKHO Problem

We are given an array ofm knapsacks, each one of capacity bℓ, for ℓ=1,…,m. There is a single item that we are asked to insert at most K times in the knapsacks array, where K is a natural given as part of the input. The profit and weight of an insertion depend on the knapsack in which we insert for i=1,…,m the naturals wi and pi represent the weight and the profit of an insertion in the knapsack i. The main feature of  IK problems is that every insertion has also an influence on the weight and profit of the nearby knapsacks. In this way, the weight charged on and the profit relative to a knapsack are established by the insertions in all the knapsacks. To describe this mechanism, Aho introduces a function (called interactive function) Ii for each knapsack i=1,…,m, that determines the interaction from a knapsack i to every other knapsack. In particular, given naturals c and u, for each knapsack i, we know that
(1)Ii(l)=1forknapsacksl∈[i,i+c],Ii(l)∈Qarbitraryforknapsacksl∈[i-u,i-1]∪[i+c+1,i+c+u],Ii(l)=0forallotherknapsacks.
The range [i,i+c] is called cloning block and the range [i-u,i-1]∪[i+c+1,i+c+u]  radiation  part. The role of the functions Ii gets clear in formulas (2)–(5).The decision variables used to denote in which knapsacks we do the insertions arexi∈{0,1} for i=1,…,m. Given in input m,pi,wi,bi,c,u∈ℕ and K∈ℕ∖{0}, an IKHO problem is to (2)maximize∑i=1mxi∑l=1mIi(l)pl(3)subjectto∑i=1mxiIi(l)wi≤bl,forl=1,…,m,(4)∑i=1mxi≤K,(5)xj=0,fori<j≤i+c,whenxi=1,
where i=1,…,m in (5). Clearly, since a feasible x must belong to {0,1}m, then at most one item may be put in each single knapsack. Moreover, notice that in Constraint (3), imposing that the knapsacks are not overfilled, Ii(ℓ) is multiplied by the weight wi. Thus, when we insert in the knapsack i(xi=1), the weight wi is equivalently charged on the knapsacks ℓ∈[i,i+c], for which Ii(ℓ)=1. This is the reason of calling the range [i,i+c]cloning block. Regarding the knapsacks in the radiation part [i-u,i-1]∪[i+c+1,i+c+u], we get that an arbitrary portion of the weight wi is added or subtracted (since Ii(ℓ) can be negative) to them. Similar operations are performed in the maximization function (2) with the profits pℓ. Furthermore, Constraint (4) specifies the maximum number of cloning blocks to be put into the knapsacks array, while Constraint (5) tells that the cloning blocks must be disjoint. The IKHO model is more widely explained and motivated in [1, 4].


### 2.1. Simplifying the Formulation

Our first step here is to simplify the formulation of the problem by making the notion of weight independent from the interaction functions, and the profit dependent only on the knapsack where we insert. This is accomplished by exploiting the transformation proposed by Aho in [2], in order to reduce IKHO to MDKP, an IPL formulation surveyed in [5]. We define
(6)pi′=∑l=1mIi(l)pl,wil′=Ii(l)wi,
so that pi′ represents the total profit of an insertion in the knapsack i, and wiℓ′ is the weight that an insertion in the knapsack i charges over the knapsack ℓ. From the features of Ii(ℓ) exposed in (1), it follows that wiℓ′ and pi′ are both rational numbers. Thus, notice that they can be also negative.Now, we can reformulate the problem as follows:(7)maximize∑i=1mxipi′(8)subjectto∑i=1mxiwil′≤bl,forl=1,…,m,(4)and(5).
Henceforth we refer always to the latter formulation of the problem, since it simplifies the description of the algorithm.Let us restate the behavior of parameterw′ as inherited by functions Ii. For i=1,…,m, we have that
(9)wil′=wi(andthenitisconstant)forl∈[i,i+c],wil′isarbitraryforl∈[i-u,i-1]∪[i+c+1,i+c+u],wil′=0forallotherl∈[1,…,m].


### 2.2. Polynomial Time Instances

The classes of instances isolated by Aho are the following:(a)
the instances withc=u=0;(b)
those withK=O(1);(c)
those withu=0;(d)
those withc+2u+1=O(log(mα)), for a constant α.The restriction of IKHO obtained by considering only the instances in (a) corresponds to the situation in which there are no interactions, whence the decision on whether to insert an item can be taken independently on each knapsack. As for (b), notice that any instance of IKHO admits at mostmK feasible solutions, which is only a polynomial number of possibilities whenever K=O(1). We refer to [3] for details on Aho's algorithm for instances of type (c) and (d).In Section3, we describe an algorithm for IKHO that has time complexity of O(m×K×c(c+2u)/c). When (c+2u)/c is bounded by a constant, it clearly becomes a polynomial time algorithm. Indeed, note that the term c(c+2u)/c is polynomial also when c+2u=O(ln(mα)), for a constant α. In fact, c(c+2u)/c=(c1/c)c+2u, and c1/c is a decreasing function on c. Therefore, our results imply those reported in (a), (c), and (d).


## 2.1. Simplifying the Formulation

Our first step here is to simplify the formulation of the problem by making the notion of weight independent from the interaction functions, and the profit dependent only on the knapsack where we insert. This is accomplished by exploiting the transformation proposed by Aho in [2], in order to reduce IKHO to MDKP, an IPL formulation surveyed in [5]. We define
(6)pi′=∑l=1mIi(l)pl,wil′=Ii(l)wi,
so that pi′ represents the total profit of an insertion in the knapsack i, and wiℓ′ is the weight that an insertion in the knapsack i charges over the knapsack ℓ. From the features of Ii(ℓ) exposed in (1), it follows that wiℓ′ and pi′ are both rational numbers. Thus, notice that they can be also negative.Now, we can reformulate the problem as follows:(7)maximize∑i=1mxipi′(8)subjectto∑i=1mxiwil′≤bl,forl=1,…,m,(4)and(5).
Henceforth we refer always to the latter formulation of the problem, since it simplifies the description of the algorithm.Let us restate the behavior of parameterw′ as inherited by functions Ii. For i=1,…,m, we have that
(9)wil′=wi(andthenitisconstant)forl∈[i,i+c],wil′isarbitraryforl∈[i-u,i-1]∪[i+c+1,i+c+u],wil′=0forallotherl∈[1,…,m].


## 2.2. Polynomial Time Instances

The classes of instances isolated by Aho are the following:(a)
the instances withc=u=0;(b)
those withK=O(1);(c)
those withu=0;(d)
those withc+2u+1=O(log(mα)), for a constant α.The restriction of IKHO obtained by considering only the instances in (a) corresponds to the situation in which there are no interactions, whence the decision on whether to insert an item can be taken independently on each knapsack. As for (b), notice that any instance of IKHO admits at mostmK feasible solutions, which is only a polynomial number of possibilities whenever K=O(1). We refer to [3] for details on Aho's algorithm for instances of type (c) and (d).In Section3, we describe an algorithm for IKHO that has time complexity of O(m×K×c(c+2u)/c). When (c+2u)/c is bounded by a constant, it clearly becomes a polynomial time algorithm. Indeed, note that the term c(c+2u)/c is polynomial also when c+2u=O(ln(mα)), for a constant α. In fact, c(c+2u)/c=(c1/c)c+2u, and c1/c is a decreasing function on c. Therefore, our results imply those reported in (a), (c), and (d).


## 3. The Algorithm

In the following,A=(m,b,c,u,w′,p′,K) always denotes the input IKHO instance. Let L∶=c+2u. A binary string s∈{0,1}L is called a signature if it obeys Constraint (5), that is, if si+sj≤1 for all i,j∈[1,L] such that 1≤|i-j|≤c. We denote by 𝒮 the set of all signatures.Given a solutionx∈{0,1}m, |x|∶=∑i=1mxi denotes the number of insertions prescribed by x. Moreover, for each ℓ∈[1,m], w(x,ℓ)∶=∑i=1mxiwiℓ′ is the weight charged on the knapsack ℓ by the solution x. Then, we say that a solution x obeys the capacity constraint (Constraint (8)) on the knapsacks [α,β] if and only if w(x,ℓ)≤bℓ for each ℓ∈[α,β]. Furthermore, we write x⊢(s,h) when xh+j=sj for each j∈[1,L] and xi=0 for each i∈[1,h], that is, when x  starts  with the signature s in the knapsacks [h+1,h+L], whence having the form x=0⋯0︸hsx′.


### 3.1. The Subproblems of Our DP Approach

Given a naturalk≤K, a natural h≤m-L, and a signature s, we consider a modified problem Sub[k,h,s], whose solutions are those x∈{0,1}m which obey
(10)x⊢(s,h),(11)w(x,l)≤bl∀l∈[h+c+u+1,m],(12)|x|≤k,and(5).
The objective function is the same as in the IKHO formulation. The differences between the IKHO problem and the above-defined subproblems are in the additional parameters s, h, k and their use in the constraints.  (i)
Constraint (10) fixes the first insertions in compliance to the signature s.(ii)
The range on which we check the capacity constraint in (11) is [h+c+u+1,m], a subset of the range [1,m] checked in IKHO.(iii)
By Constraint (12), we can do at most k insertions. Notice that in general (12) is more restrictive than (4).In the following, we denote by𝒳[A] the space of solutions to the IKHO instance A, and by 𝒳[k,h,s] the space of solutions to the modified problem Sub[k,h,s]. Moreover, let opt[A] be the maximum value of a solution in 𝒳[A] and opt[k,h,s] the maximum value of a solution in 𝒳[k,h,s]. It is assumed that opt[k,h,s]=-∞ when 𝒳[k,h,s] is empty.


### 3.2. The Dynamic Programming Algorithm

Our dynamic programming approach is based on Lemmas1 and 2, whose proofs are given later in this subsection. In particular, Lemma 1 shows how to read out an optimal solution to the IKHO instance, from the optimal solutions to the subproblems.Lemma 1.
Let𝒮0⊆𝒮 be the set of the signatures s such that y=s·0m-L obeys the capacity constraint on all knapsacks ℓ∈[1,c+u]. Then,
(13)opt[A]=max⁡s∈S0⁡opt[K,0,s].
Indeed, 𝒳[A]=⋃s∈𝒮0𝒳[K,0,s].Lemma2 explains how to recursively solve the subproblems. We need some additional notation. Given x∈{0,1}m, b∈{0,1}, for i=1,…,m, we write x+(b,i) to denote the binary string obtained from x by setting its i-th element to b. Moreover, if X⊆{0,1}m, we let X+(b,i)∶={x+(b,i):x∈X}. Furthermore, for each b∈{0,1}, and h∈[0,m-L], a signature s∈𝒮 is called (h,b)-good if z∶=0h·s·b·0m-h-L-1 obeys the capacity constraint for the knapsack h+c+u+1 and if s′∶=(s2,s3,…,sL,b)∈𝒮.Lemma 2.
Fork=1,…,K, h=0,…,m-L-1, s∈𝒮,
(14)opt[k,h,s]=max⁡b∈{0,1}:sis(h,b)-good⁡opt×[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+s1ph+1′.
Indeed,
(15)X[k,h,s]=⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1).The base for the recursion, that is, the cases whereh=m-L and k=0, is handled in Section 3.3.In order to prove Lemmas1 and 2, let us begin by pointing out some basic facts that directly derive from the IKHO formulation. Observations 1 and 2 play an important role in the formal proofs of these lemmas. For this reason, these observations and their proofs are visualized in Figures 1 and 2, respectively.Figure 1
Representing Observation1. The gray area indicates where x is equal to y, that is, the knapsacks [1,a]. The arrow represents the left most possible radiation as starting from the left most possible different bit. Since this radiation cannot reach the knapsacks [1,a-u], then, for ℓ∈[1,a-u], w(x,ℓ) and w(y,ℓ) cannot differ as they depend only on the common bits [1,a].Figure 2
Representing Observation2.Observation 1.
Assumea>u. Let x,y∈{0,1}m such that xi=yi for i=1,…,a. Then, for each ℓ≤a-u, x satisfies the capacity constraint if and only if y satisfies it. Indeed, for each ℓ≤a-u, w(x,ℓ)=w(y,ℓ).Proof.
Letℓ≤a-u. Remember that w(x,ℓ)∶=∑i=1mxiwiℓ′. However, by (9), wiℓ′=0 for ℓ<i-u, that is, when i>l+u. Moreover, xi=yi for i=1,…,ℓ+u, since ℓ+u≤a. Therefore,
(16)w(x,l)∶=∑i=1mxiwil′=∑i=1l+uxiwil′=∑i=1l+uyiwil′=∑i=1myiwil′=:w(y,l).Observation2 covers the left/right-reverse situation.Observation 2.
Assumea≤m-c-u. Let x,y∈{0,1}m such that xi=yi for each i=a,…,m. Then, for each ℓ≥a+c+u, x satisfies the capacity constraint if and only if y satisfies it. Indeed, for each ℓ≥a+c+u, w(x,ℓ)=w(y,ℓ).Proof.
Letℓ≥a+c+u. By (9), wiℓ′=0 for ℓ>i+c+u, that is, when i<l-c-u. Moreover, xi=yi for i=ℓ-c-u,…,m, since ℓ-c-u≥a. Therefore,
(17)w(x,l)∶=∑i=1mxiwil′=∑i=l-c-umxiwil′=∑i=l-c-umyiwil′=∑i=1myiwil′=:w(y,l).Now, we are ready to prove Lemmas1 and 2.Proof of Lemma1.
First, let us show that every feasible solution to IKHO is a feasible solution to one of the subproblemsSub[K,0,s] for an s∈𝒮0. Clearly, for each x∈𝒳[A], taking s∶=(x1,x2,…,xL), we get that x∈𝒳[K,0,s]. By exploiting Observation 1 with a=L, we get that y∶=s·0m-L obeys the capacity constraint on knapsacks [1,c+u], and then s∈𝒮0. To prove the opposite inclusion, take s∈𝒮0 and x∈𝒳[K,0,s]. We show that x∈𝒳[A]. Constraint (4), Constraint (5), and the capacity constraint on knapsacks [c+u+1,m] are clearly satisfied. Since s∈𝒮0, Observation 1 let us verify the capacity constraint on knapsacks [1,c+u].Lemma2 directly follows from the two opposite inclusions, that we show separately. While reading these proofs, Figure 3 can be useful to visualize the structure of the vectors x,y involved in the proofs.Figure 3
Building a feasible solution toSub[k,h,s]. In order to construct a feasible solution x to the current subproblem Sub[k,h,s], we exploit a feasible solution y to one of the subsequent subproblems Sub[k-s1,h+1,s′∶=(s2,s3,…,sL,b)], for a b∈{0,1}. Clearly, x must satisfy the capacity constraint on the knapsacks [h+c+u+1,m]. Moreover, notice that the radiation from the bit s1 does not reach the knapsacks after h+c+u+1, and then, for those knapsacks, x satisfies the capacity constraint only if y does. Therefore, we need to check the capacity constraint only for the knapsack h+c+u+1. Furthermore, the bits after b are not involved when we check the capacity constraint on that knapsack. Thus, in order to check the capacity constraint on the knapsack h+c+u+1, it is enough to know the bits of the string s·b. Notice that, for a signature s,L is the smallest width that holds the properties we showed above.Proof of Lemma2.
First, we show that(18)X[k,h,s]⊆⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1).
Proof.
Supposex∈𝒳[k,h,s]. Let b∶=xh+L+1. The inclusion follows by two facts:  (a)
s is (h,b)-good;(b)
x∈𝒳[k-s1,h+1,s′]+(s1,h+1). Take z∶=0h·s·b·0m-h-L-1. Since x obeys the capacity constraint on knapsacks [h+c+u+1,m] and xi=zi for i=1,…,h+L+1, by exploiting Observation 1 with a=h+L+1, we get that z satisfies the capacity constraint on the knapsack h+c+u+1. Clearly, s′∶=(s2,s3,…,sL,b) satisfies Constraint (5), being a substring of x. Hence, s is (h,b)-good.
In order to show thatx∈𝒳[k-s1,h+1,s′]+(s1,h+1), we take y∶=x+(0,h+1) and we show that y∈𝒳[k-s1,h+1,s′]. By following the subproblems definition, it is simple to verify that y obeys Constraint (10), (12), and (5) of Sub[k-s1,h+1,s′]. Moreover, since x satisfies the capacity constraint for each ℓ∈[h+c+u+1,m], by applying Observation 2 with a=h+2, we get that y satisfies the capacity constraint over the knapsacks [h+c+u+2,m], and then y obeys Constraint (11) too.Second, we prove that(19)⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1)⊆X[k,h,s].Proof.
Take ab∈{0,1} such that s is (h,b)-good and a y∈𝒳[k-s1,h+1,s′∶=s2,s3,…,sL,b]. We will show that x∶=y+(s1,h+1)∈𝒳[k,h,s]. Constraint (10) and (12) of Sub[k,h,s] easily follow from subproblems definition. Moreover, since y satisfies Constraint (5) and s∈𝒮, then x satisfies Constraint (5).
It remains to verify Constraint (11). Since s is (h,b)-good, then z∶=0h·s·b·0m-h-L-1 obeys the capacity constraint on the knapsack h+c+u+1. By applying Observation 1 with a=h+L+1, we derive that also x obeys the capacity constraint on that knapsack. Moreover, since y∈𝒳[k-s1,h+1,s′], then y obeys the capacity constraint on the knapsacks [h+c+u+2,m]. Since yi=xi for i=(h+2,…,m), by Observation 2,  x obeys the capacity constraint also for the knapsacks [h+c+u+2,m].


### 3.3. The Base of the Recursion

We have two base cases. Observation3 handles the case when h=m-L, while Observation 4 treats the case when k=0.Observation 3.
Considerh=m-L, for all k=1,…,K, and s∈𝒮. Moreover, let z∶=0h·s. If|z|≤kand w(z,ℓ)≤bℓ for each ℓ∈[m-u+1,m],thenopt[k,h,s]=∑i=1mzipi′. Otherwise, opt[k,h,s]=-∞.Proof.
Clearly, sinceh+L=m and by Constraint (10), there cannot exist a solution to Sub[k,h,s] different from z. Moreover, notice that h+c+u+1=m-u+1.Observation 4.
Considerk=0, for all h=0,…,m-L, and s∈𝒮. Ifs=0L, then opt[k,h,s]=0,Otherwiseopt[k,h,s]=-∞.Proof.
Clearly, by Constraint (12), 0m can be the only solution to Sub[0,h,s].


## 3.1. The Subproblems of Our DP Approach

Given a naturalk≤K, a natural h≤m-L, and a signature s, we consider a modified problem Sub[k,h,s], whose solutions are those x∈{0,1}m which obey
(10)x⊢(s,h),(11)w(x,l)≤bl∀l∈[h+c+u+1,m],(12)|x|≤k,and(5).
The objective function is the same as in the IKHO formulation. The differences between the IKHO problem and the above-defined subproblems are in the additional parameters s, h, k and their use in the constraints.  (i)
Constraint (10) fixes the first insertions in compliance to the signature s.(ii)
The range on which we check the capacity constraint in (11) is [h+c+u+1,m], a subset of the range [1,m] checked in IKHO.(iii)
By Constraint (12), we can do at most k insertions. Notice that in general (12) is more restrictive than (4).In the following, we denote by𝒳[A] the space of solutions to the IKHO instance A, and by 𝒳[k,h,s] the space of solutions to the modified problem Sub[k,h,s]. Moreover, let opt[A] be the maximum value of a solution in 𝒳[A] and opt[k,h,s] the maximum value of a solution in 𝒳[k,h,s]. It is assumed that opt[k,h,s]=-∞ when 𝒳[k,h,s] is empty.


## 3.2. The Dynamic Programming Algorithm

Our dynamic programming approach is based on Lemmas1 and 2, whose proofs are given later in this subsection. In particular, Lemma 1 shows how to read out an optimal solution to the IKHO instance, from the optimal solutions to the subproblems.Lemma 1.
Let𝒮0⊆𝒮 be the set of the signatures s such that y=s·0m-L obeys the capacity constraint on all knapsacks ℓ∈[1,c+u]. Then,
(13)opt[A]=max⁡s∈S0⁡opt[K,0,s].
Indeed, 𝒳[A]=⋃s∈𝒮0𝒳[K,0,s].Lemma2 explains how to recursively solve the subproblems. We need some additional notation. Given x∈{0,1}m, b∈{0,1}, for i=1,…,m, we write x+(b,i) to denote the binary string obtained from x by setting its i-th element to b. Moreover, if X⊆{0,1}m, we let X+(b,i)∶={x+(b,i):x∈X}. Furthermore, for each b∈{0,1}, and h∈[0,m-L], a signature s∈𝒮 is called (h,b)-good if z∶=0h·s·b·0m-h-L-1 obeys the capacity constraint for the knapsack h+c+u+1 and if s′∶=(s2,s3,…,sL,b)∈𝒮.Lemma 2.
Fork=1,…,K, h=0,…,m-L-1, s∈𝒮,
(14)opt[k,h,s]=max⁡b∈{0,1}:sis(h,b)-good⁡opt×[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+s1ph+1′.
Indeed,
(15)X[k,h,s]=⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1).The base for the recursion, that is, the cases whereh=m-L and k=0, is handled in Section 3.3.In order to prove Lemmas1 and 2, let us begin by pointing out some basic facts that directly derive from the IKHO formulation. Observations 1 and 2 play an important role in the formal proofs of these lemmas. For this reason, these observations and their proofs are visualized in Figures 1 and 2, respectively.Figure 1
Representing Observation1. The gray area indicates where x is equal to y, that is, the knapsacks [1,a]. The arrow represents the left most possible radiation as starting from the left most possible different bit. Since this radiation cannot reach the knapsacks [1,a-u], then, for ℓ∈[1,a-u], w(x,ℓ) and w(y,ℓ) cannot differ as they depend only on the common bits [1,a].Figure 2
Representing Observation2.Observation 1.
Assumea>u. Let x,y∈{0,1}m such that xi=yi for i=1,…,a. Then, for each ℓ≤a-u, x satisfies the capacity constraint if and only if y satisfies it. Indeed, for each ℓ≤a-u, w(x,ℓ)=w(y,ℓ).Proof.
Letℓ≤a-u. Remember that w(x,ℓ)∶=∑i=1mxiwiℓ′. However, by (9), wiℓ′=0 for ℓ<i-u, that is, when i>l+u. Moreover, xi=yi for i=1,…,ℓ+u, since ℓ+u≤a. Therefore,
(16)w(x,l)∶=∑i=1mxiwil′=∑i=1l+uxiwil′=∑i=1l+uyiwil′=∑i=1myiwil′=:w(y,l).Observation2 covers the left/right-reverse situation.Observation 2.
Assumea≤m-c-u. Let x,y∈{0,1}m such that xi=yi for each i=a,…,m. Then, for each ℓ≥a+c+u, x satisfies the capacity constraint if and only if y satisfies it. Indeed, for each ℓ≥a+c+u, w(x,ℓ)=w(y,ℓ).Proof.
Letℓ≥a+c+u. By (9), wiℓ′=0 for ℓ>i+c+u, that is, when i<l-c-u. Moreover, xi=yi for i=ℓ-c-u,…,m, since ℓ-c-u≥a. Therefore,
(17)w(x,l)∶=∑i=1mxiwil′=∑i=l-c-umxiwil′=∑i=l-c-umyiwil′=∑i=1myiwil′=:w(y,l).Now, we are ready to prove Lemmas1 and 2.Proof of Lemma1.
First, let us show that every feasible solution to IKHO is a feasible solution to one of the subproblemsSub[K,0,s] for an s∈𝒮0. Clearly, for each x∈𝒳[A], taking s∶=(x1,x2,…,xL), we get that x∈𝒳[K,0,s]. By exploiting Observation 1 with a=L, we get that y∶=s·0m-L obeys the capacity constraint on knapsacks [1,c+u], and then s∈𝒮0. To prove the opposite inclusion, take s∈𝒮0 and x∈𝒳[K,0,s]. We show that x∈𝒳[A]. Constraint (4), Constraint (5), and the capacity constraint on knapsacks [c+u+1,m] are clearly satisfied. Since s∈𝒮0, Observation 1 let us verify the capacity constraint on knapsacks [1,c+u].Lemma2 directly follows from the two opposite inclusions, that we show separately. While reading these proofs, Figure 3 can be useful to visualize the structure of the vectors x,y involved in the proofs.Figure 3
Building a feasible solution toSub[k,h,s]. In order to construct a feasible solution x to the current subproblem Sub[k,h,s], we exploit a feasible solution y to one of the subsequent subproblems Sub[k-s1,h+1,s′∶=(s2,s3,…,sL,b)], for a b∈{0,1}. Clearly, x must satisfy the capacity constraint on the knapsacks [h+c+u+1,m]. Moreover, notice that the radiation from the bit s1 does not reach the knapsacks after h+c+u+1, and then, for those knapsacks, x satisfies the capacity constraint only if y does. Therefore, we need to check the capacity constraint only for the knapsack h+c+u+1. Furthermore, the bits after b are not involved when we check the capacity constraint on that knapsack. Thus, in order to check the capacity constraint on the knapsack h+c+u+1, it is enough to know the bits of the string s·b. Notice that, for a signature s,L is the smallest width that holds the properties we showed above.Proof of Lemma2.
First, we show that(18)X[k,h,s]⊆⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1).
Proof.
Supposex∈𝒳[k,h,s]. Let b∶=xh+L+1. The inclusion follows by two facts:  (a)
s is (h,b)-good;(b)
x∈𝒳[k-s1,h+1,s′]+(s1,h+1). Take z∶=0h·s·b·0m-h-L-1. Since x obeys the capacity constraint on knapsacks [h+c+u+1,m] and xi=zi for i=1,…,h+L+1, by exploiting Observation 1 with a=h+L+1, we get that z satisfies the capacity constraint on the knapsack h+c+u+1. Clearly, s′∶=(s2,s3,…,sL,b) satisfies Constraint (5), being a substring of x. Hence, s is (h,b)-good.
In order to show thatx∈𝒳[k-s1,h+1,s′]+(s1,h+1), we take y∶=x+(0,h+1) and we show that y∈𝒳[k-s1,h+1,s′]. By following the subproblems definition, it is simple to verify that y obeys Constraint (10), (12), and (5) of Sub[k-s1,h+1,s′]. Moreover, since x satisfies the capacity constraint for each ℓ∈[h+c+u+1,m], by applying Observation 2 with a=h+2, we get that y satisfies the capacity constraint over the knapsacks [h+c+u+2,m], and then y obeys Constraint (11) too.Second, we prove that(19)⋃b∈{0,1}:sis(h,b)-goodX[k-s1,h+1,s′∶=(s2,s3,…,sL,b)]+(s1,h+1)⊆X[k,h,s].Proof.
Take ab∈{0,1} such that s is (h,b)-good and a y∈𝒳[k-s1,h+1,s′∶=s2,s3,…,sL,b]. We will show that x∶=y+(s1,h+1)∈𝒳[k,h,s]. Constraint (10) and (12) of Sub[k,h,s] easily follow from subproblems definition. Moreover, since y satisfies Constraint (5) and s∈𝒮, then x satisfies Constraint (5).
It remains to verify Constraint (11). Since s is (h,b)-good, then z∶=0h·s·b·0m-h-L-1 obeys the capacity constraint on the knapsack h+c+u+1. By applying Observation 1 with a=h+L+1, we derive that also x obeys the capacity constraint on that knapsack. Moreover, since y∈𝒳[k-s1,h+1,s′], then y obeys the capacity constraint on the knapsacks [h+c+u+2,m]. Since yi=xi for i=(h+2,…,m), by Observation 2,  x obeys the capacity constraint also for the knapsacks [h+c+u+2,m].


## 3.3. The Base of the Recursion

We have two base cases. Observation3 handles the case when h=m-L, while Observation 4 treats the case when k=0.Observation 3.
Considerh=m-L, for all k=1,…,K, and s∈𝒮. Moreover, let z∶=0h·s. If|z|≤kand w(z,ℓ)≤bℓ for each ℓ∈[m-u+1,m],thenopt[k,h,s]=∑i=1mzipi′. Otherwise, opt[k,h,s]=-∞.Proof.
Clearly, sinceh+L=m and by Constraint (10), there cannot exist a solution to Sub[k,h,s] different from z. Moreover, notice that h+c+u+1=m-u+1.Observation 4.
Considerk=0, for all h=0,…,m-L, and s∈𝒮. Ifs=0L, then opt[k,h,s]=0,Otherwiseopt[k,h,s]=-∞.Proof.
Clearly, by Constraint (12), 0m can be the only solution to Sub[0,h,s].


## 4. Complexity

In this section, we prove Lemma3.Lemma 3.
Letr be a constant such that L/c is bounded by r when c>0, and L is bounded by r when c=0. The above algorithm takes time and space of O(cr×m×K).Clearly, our algorithm exploits a three-dimensional matrix for storing the valuesopt[k,h,s], for k=1,…,K, h=0,…,m-L, and s∈𝒮. We also need a matrix of the same size which traces, for each subproblem Sub[k,h,s], the subsequent subproblem used to compute opt[k,h,s]. This makes us rebuild the optimum solution at the end. The space complexity of the algorithm then is O(K×m×|𝒮|). We need to rate the value of |𝒮|, but first let us to compute the time complexity.In order to evaluate the base case of our dynamic programming algorithm, we first refer to Observation3. Clearly, for k<|s|, opt[k,h,s]=-∞, because there must be at least |s| insertion in a solution that starts with the signature s. Moreover, since z∶=0h·s is the only feasible solution to Sub[k,h,s], it is clear that, for each k>|s|, opt[k,h,s]=opt[|s|,h,s], by Constraint (12). Therefore, we have to compute only for k=|s|, and then, the number of base case subproblems to be computed is only |𝒮|. Since s∈{0,1}L, L is the time needed for computing both the profit of z and w(z,ℓ), for an ℓ∈[m-u+1,m]. Then, to check the capacity constraint on all the knapsacks [m-u+1,m], we need u×L computations. Thus, the base case h=m-L can be computed in time of O(|𝒮|×L×u). About the base case k=0, as handled by Observation 4, note that if we codify the signatures s∈𝒮 (a such codify is given in Section 4.2), we can check the condition s=0L in O(1). Regarding the general case, by (14), for solving a subproblem, we have to check if s is (h,b)-good, for b=0,1. To check if z∶=0h·s·b·0m-h-L-1 satisfies the capacity constraint on the knapsack h+c+u+1, and if s′∈𝒮, we spend O(L) computations. Since the number of subproblems is K×(m-L)×|𝒮|, we need O(|𝒮|×m×L×K) time to fill the matrix opt. Moreover, by (13), we have to scan over the s∈𝒮0 in order to find the maximum value of opt[K,0,s]. Clearly, |𝒮0|≤|𝒮|, but we need L×(c+u) computations to check the capacity constraints on all knapsacks ℓ∈[1,c+u], because each signature s has width L. Thus, we spend O(|𝒮|×L2) computations, to find opt[A]. Furthermore, rebuilding the best solution takes O(m) time. Therefore, the part in which we recursively compute the subproblems leads the complexity of the entire algorithm. It depends on the value of |𝒮|, as well as the space complexity. In Section 4.1, we give an estimate of this value. Moreover, in Section 4.2, we show an ordering of the set 𝒮, that permits us to check the capacity constraint on a knapsack in constant time.


### 4.1. Estimating|𝒮|

In the case wherec is a constant, we can directly estimate |𝒮|.Observation 5.
Ifc is a constant, then |𝒮|=O(1).Proof.
Clearly,|𝒮|≤2L, because the number of binary strings s∈{0,1}L is 2L. Moreover, when c=0, we supposed L constant. When c>0, since L/c≤r, we get that L≤rc, with constant r and c.For nonconstant values ofc, let us find a general form for |𝒮|. Let Sc(n) denote the number of binary strings s∈{0,1}n such that s obeys Constraint (5). Note that Constraint (5) contains the parameter c. When n∈[0,c], we have n places where to insert, and at most one insertion is possible by Constraint (5). Moreover, we have to count the string with no insertions. Thus, we get that Sc(n)=n+1 for all n∈[0,c]. For greater values of n, we refer to the recursion shown in Figure 4. If the first bit of s is 0, the choice of the following bits is not influenced. Therefore, it is enough to find the number of strings s∈{0,1}n-1 such that s obeys Constraint (5), that is exactly Sc(n-1). If the first bit is 1, by Constraint (5), the following c bits are necessarily 0’s. In this case, we continue to choose after the c+1-th bit. Thus, we have Sc(n-c-1) ways to choose the remaining bits. Therefore, we can express Sc(n) by the recurrence equation: (20)Sc(n)=Sc(n-1)+Sc(n-c-1),Sc(n)=n+1∀n∈[0,c].Figure 4
The influence of the first bit choice.Lemma4 gives a general estimate of the recurrence Sc(n), in order to bound |𝒮| for nonconstant values of c.Lemma 4.
Letc≥e. For each n≥c, Sc(n)≤((c+1)/c)cn/c.Proof.
We prove the claim by induction onn, and we postpone to the appendix the proof of the base of the induction, that is, the case c≤n≤2c. For n>2c, we have the step of induction. Clearly,
(21)Sc(n)=Sc(n-1)+Sc(n-c-1)≤c+1cc(n-1)/c+c+1cc(n-c-1)/c=c+1c(c(n-1)/c+c(n-c-1)/c)=c+1cc(n-c-1)/c(1+cc/c)=c+1cc(n-c-1)/c(1+c)=c+1ccn/c(1+c)c(c+1)/c.
Hence, it is sufficient to show that (1+c)/c(c+1)/c≤1 or equivalently 1+c≤c(c+1)/c. Since c(c+1)/c=c·c1/c, it remains to show that (1+1/c)≤c1/c.
We know thatex≥x+1 for each real x. By substituting x with 1/c and noticing that c≥e, we get that (1+1/c)≤c1/c.SinceL=c+2u≥c, we can apply Lemma 4 to deduce that |𝒮|=Sc(L)=O(cL/c), as (c+1)/c≤2 for c>0. Therefore, when L/c is bounded by a constant r, we get |𝒮|=O(cr).


### 4.2. Ranking the Set𝒮

We use Recurrence (20) to define a function pos:𝒮→[0,|𝒮|-1], which provides a unique index for each signature, and hence, it gives a ranking for the set 𝒮.Definition 5.
For eachs∈𝒮,
(22)pos(s)∶=∑i=1Lsi⋅Sc(L-i).Note thatSc(L-i) is the number of signatures having length L-i, and it is equivalent to the number of signatures of length L-i+1 that start with a 0. Hence, as illustrated in Figure 5, in the step of the sum where i=1, we intend to place the signatures with s1=1 after all the signatures with s1=0, that are exactly Sc(L-1). For i=2,…,L, we do recursively the same, locating substrings of length L-i.Figure 5
Ordering the signatures.Conversely, given an integerp∈[0,|S|-1], the unranking procedure is the following. Take s∶=0L. For i=1,…,L, if p≥Sc(L-i), set si=1 and p∶=p-Sc(L-i).Evidently, in order to efficiently perform such ordering on the set𝒮, we need to compute and store the recurrence Sc(n), for n=1,…,L-1, at the beginning of the algorithm. This takes O(L) time and space, whereas the ranking and unranking operations take O(L) time.Indeed, we can avoid to encode and decode the signatures for the computation of each subproblem. This can be done by initializing a table at the beginning of the algorithm, that stores, for each positionpos(s′) relative to a signature s′, a list of the bits that are changed from the previous signature s, that is, the signature having pos(s)=pos(s′)-1. It is easy to verify the following procedure finds the next signature from the previous one (it works similarly to the function that increments a binary counter, but considering Constraint (5)).  (i)
Scan the previous strings starting from the least significant bit (right most) and find the first range of c+1 consecutive 0’s, or a range of consecutive 0’s that includes the most significant bit (left most).(ii)
If such a range exists, the next string is obtained by setting to 1 the right most bit of the range, and by setting to 0 all the bits at the right of the range.(iii)
If such a range does not exist,s is the last signature.Above all, observe that, by Constraint (5), there are at most L/(c+1) insertions in a signature s∈|𝒮|, and we know that L/(c+1)≤L/c≤r. Therefore, for every kind of ranking for the set 𝒮, the number of the bits changing between two adjacent signatures is O(r). Thus, if we know the changing bits from a signature s to the next s′, we can use an incremental approach for computing the value w(s′,ℓ), from w(s,ℓ), in constant time. This allows us to check in constant time the capacity constraints of the (h,b)-goodness (14), those regarding the definition of the set 𝒮0 (13), and when computing the base case (Observation 3). Note that also Constraint (5) of the (h,b)-goodness can be computed in O(r) with the same technique.Moreover, note that when computing the matrixopt, if we place the cycle on the variable s, externally to the cycle on the variable k, we can clearly find the next signature and check the capacity constraints only once every K subproblems. In this way, the cost of finding the next signature is made inessential.Thus, we can conclude that our algorithm has time and space complexity ofO(cr×m×K).


## 4.1. Estimating|𝒮|

In the case wherec is a constant, we can directly estimate |𝒮|.Observation 5.
Ifc is a constant, then |𝒮|=O(1).Proof.
Clearly,|𝒮|≤2L, because the number of binary strings s∈{0,1}L is 2L. Moreover, when c=0, we supposed L constant. When c>0, since L/c≤r, we get that L≤rc, with constant r and c.For nonconstant values ofc, let us find a general form for |𝒮|. Let Sc(n) denote the number of binary strings s∈{0,1}n such that s obeys Constraint (5). Note that Constraint (5) contains the parameter c. When n∈[0,c], we have n places where to insert, and at most one insertion is possible by Constraint (5). Moreover, we have to count the string with no insertions. Thus, we get that Sc(n)=n+1 for all n∈[0,c]. For greater values of n, we refer to the recursion shown in Figure 4. If the first bit of s is 0, the choice of the following bits is not influenced. Therefore, it is enough to find the number of strings s∈{0,1}n-1 such that s obeys Constraint (5), that is exactly Sc(n-1). If the first bit is 1, by Constraint (5), the following c bits are necessarily 0’s. In this case, we continue to choose after the c+1-th bit. Thus, we have Sc(n-c-1) ways to choose the remaining bits. Therefore, we can express Sc(n) by the recurrence equation: (20)Sc(n)=Sc(n-1)+Sc(n-c-1),Sc(n)=n+1∀n∈[0,c].Figure 4
The influence of the first bit choice.Lemma4 gives a general estimate of the recurrence Sc(n), in order to bound |𝒮| for nonconstant values of c.Lemma 4.
Letc≥e. For each n≥c, Sc(n)≤((c+1)/c)cn/c.Proof.
We prove the claim by induction onn, and we postpone to the appendix the proof of the base of the induction, that is, the case c≤n≤2c. For n>2c, we have the step of induction. Clearly,
(21)Sc(n)=Sc(n-1)+Sc(n-c-1)≤c+1cc(n-1)/c+c+1cc(n-c-1)/c=c+1c(c(n-1)/c+c(n-c-1)/c)=c+1cc(n-c-1)/c(1+cc/c)=c+1cc(n-c-1)/c(1+c)=c+1ccn/c(1+c)c(c+1)/c.
Hence, it is sufficient to show that (1+c)/c(c+1)/c≤1 or equivalently 1+c≤c(c+1)/c. Since c(c+1)/c=c·c1/c, it remains to show that (1+1/c)≤c1/c.
We know thatex≥x+1 for each real x. By substituting x with 1/c and noticing that c≥e, we get that (1+1/c)≤c1/c.SinceL=c+2u≥c, we can apply Lemma 4 to deduce that |𝒮|=Sc(L)=O(cL/c), as (c+1)/c≤2 for c>0. Therefore, when L/c is bounded by a constant r, we get |𝒮|=O(cr).


## 4.2. Ranking the Set𝒮

We use Recurrence (20) to define a function pos:𝒮→[0,|𝒮|-1], which provides a unique index for each signature, and hence, it gives a ranking for the set 𝒮.Definition 5.
For eachs∈𝒮,
(22)pos(s)∶=∑i=1Lsi⋅Sc(L-i).Note thatSc(L-i) is the number of signatures having length L-i, and it is equivalent to the number of signatures of length L-i+1 that start with a 0. Hence, as illustrated in Figure 5, in the step of the sum where i=1, we intend to place the signatures with s1=1 after all the signatures with s1=0, that are exactly Sc(L-1). For i=2,…,L, we do recursively the same, locating substrings of length L-i.Figure 5
Ordering the signatures.Conversely, given an integerp∈[0,|S|-1], the unranking procedure is the following. Take s∶=0L. For i=1,…,L, if p≥Sc(L-i), set si=1 and p∶=p-Sc(L-i).Evidently, in order to efficiently perform such ordering on the set𝒮, we need to compute and store the recurrence Sc(n), for n=1,…,L-1, at the beginning of the algorithm. This takes O(L) time and space, whereas the ranking and unranking operations take O(L) time.Indeed, we can avoid to encode and decode the signatures for the computation of each subproblem. This can be done by initializing a table at the beginning of the algorithm, that stores, for each positionpos(s′) relative to a signature s′, a list of the bits that are changed from the previous signature s, that is, the signature having pos(s)=pos(s′)-1. It is easy to verify the following procedure finds the next signature from the previous one (it works similarly to the function that increments a binary counter, but considering Constraint (5)).  (i)
Scan the previous strings starting from the least significant bit (right most) and find the first range of c+1 consecutive 0’s, or a range of consecutive 0’s that includes the most significant bit (left most).(ii)
If such a range exists, the next string is obtained by setting to 1 the right most bit of the range, and by setting to 0 all the bits at the right of the range.(iii)
If such a range does not exist,s is the last signature.Above all, observe that, by Constraint (5), there are at most L/(c+1) insertions in a signature s∈|𝒮|, and we know that L/(c+1)≤L/c≤r. Therefore, for every kind of ranking for the set 𝒮, the number of the bits changing between two adjacent signatures is O(r). Thus, if we know the changing bits from a signature s to the next s′, we can use an incremental approach for computing the value w(s′,ℓ), from w(s,ℓ), in constant time. This allows us to check in constant time the capacity constraints of the (h,b)-goodness (14), those regarding the definition of the set 𝒮0 (13), and when computing the base case (Observation 3). Note that also Constraint (5) of the (h,b)-goodness can be computed in O(r) with the same technique.Moreover, note that when computing the matrixopt, if we place the cycle on the variable s, externally to the cycle on the variable k, we can clearly find the next signature and check the capacity constraints only once every K subproblems. In this way, the cost of finding the next signature is made inessential.Thus, we can conclude that our algorithm has time and space complexity ofO(cr×m×K).


## 5. Memory Saving Version

Consider (14). Given an h̅∈[1,m-L-1], in order to compute opt[k,h̅,s] for each s∈𝒮 and k≤K, we need only the elements having h=h̅+1 of the matrix opt. Moreover, by (13), only the elements with h=0 are required for computing opt[A]. Thus, in order to work out the profit of a best solution, we only need O(|𝒮|×K) space. Unfortunately, this simplification does not apply to the matrix used to compute the best solution.In [6], Hirschberg showed an elegant and practical space reduction method for the longest common subsequence problem, which works for many dynamic programming algorithms (well exposed also in [7]). In general, this method allows to compute an optimal solution, taking as much space and time as if we had only to compute the optimal solution value. This is accomplished by exploiting the equation which handles the recursion in the original algorithm (in our case (14)). Its space policy exploits the space improvement mentioned at the beginning of this section.Conceptually, the basic idea of the method is to halve a dimension of the dynamic programming matrix and find how the best solution is divided in the other dimensions. This permits the two halves obtained to be solved separately and recursively in the same way. In order to apply this method to our algorithm, we follow the next steps.(i)
We halve the knapsack array.(ii)
We find how many insertions of the best solution are placed in each half of the knapsack array.(iii)
We locate a number of insertions placed around the middle of the knapsack array. This allows us to break up the IKHO problem in two independent subproblems, which are then solved recursively.Notice that, in the last sentence, the wordsubproblems does not refer to the subproblems Sub[k,h,s] defined in Section 3.In Section5.1, we implement this idea. In Section 5.2, we show that the new defined algorithm decreases the space complexity to O(|𝒮|×K), without increasing the time complexity.


### 5.1. The Algorithm

In the following, we writex⊢R(s,h) when xh-L-1+j=sj for each j∈[1,L] and xi=0 for each i∈[h,m], that is, when x  ends with the signature s in the knapsacks [h-L,h-1].Given a naturalk≤K, a natural h∈[L+1,m+1], and a signature s, we consider a modified problem SubR[k,h,s] whose solutions are those x∈{0,1}m which obey
(23)x⊢R(s,h),w(x,l)≤bl∀l∈[1,h-u-1],|x|≤k,and(5).
The subproblems SubR[k,h,s] are simply the symmetrical transposition of the subproblems Sub[k,h,s]. The only significant difference is that we check the capacity constraints in the range [1,h-u-1], that is, not symmetrical to the range [h+c+u+1,m]. This dissimilarity is caused by the fact that also the radiations produced by an insertion are not symmetrical too (see (9)).We denote by𝒳R[k,h,s] the space of the feasible solutions to the modified problem SubR[k,h,s]. Moreover, optR[k,h,s] is the maximum profit of a solution in 𝒳R[k,h,s] when 𝒳R[k,h,s] is not empty, and optR[k,h,s]=-∞ when 𝒳R[k,h,s] is empty. Notice that, since the subproblems Sub and SubR are symmetrical, the properties proved for opt hold symmetrically for optR, bringing some adjustments due to the fact that the radiations are not exactly symmetrical. Thus, for computing the matrix optR, we take the same space and time needed for computing the matrix opt, that is, O(|𝒮|×K) space and O(m×|𝒮|×K) time.In the following, let|s| to be the number of insertions in a signature s. For each s∈𝒮, and for h=0,…,m-L, let p(s,h)∶=∑i=1Lsiph+i′. Clearly, this function holds for each knapsack h the profit caused by placing the signature s in the knapsacks [h+1,…,h+L]. Moreover, for α,β=1,…,m, and y∈{0,1}m, let y(α,β) be the substring of y composed by the elements in the range [α,β] (we assume y(α,β) is empty when α<β). Furthermore, for k,k′≤K, for each signature s, for h=0,…,m-L and h′=L+1,…,m-L such that h′-h=L+1, let 𝒳R[k′,h′,s]⊗𝒳[k,h,s]∶={y′(1,h)·s·y(h′,m):y′∈𝒳R[k′,h′,s],y∈𝒳[k,h,s]}. This new operator defines a new space of solutions given by the concatenation of the feasible solutions of two symmetrical subproblems. Notice that the signature s represents the joining point when concatenating the two strings. This situation is represented in Figure 6, which is also useful to visualize the proof of Lemma 6, which represents the main innovation on our algorithm.Figure 6
Joining𝒳R[k′,h′,s] with 𝒳[k,h,s]. The solution y belongs to the space 𝒳[k,h,s], while y′∈𝒳R[k′,h′,s]. Note that the knapsacks [h+c+u+1,m], where y satisfies the capacity constraint, are complementary to the knapsacks [1,h′-u-1], where y′ satisfies that constraint.Lemma 6.
Leth=m/2-L/2-1, and h′=h+L+1.
Then,(24)opt[A]=max⁡s∈S,|s|≤k≤K⁡(optR[K-k+|s|,h′,s]+opt[k,h,s]-p(s,h)).
Indeed,
(25)X[A]=⋃s∈S,|s|≤k≤K(XR[K-k+|s|,h′,s]⊗X[k,h,s]).Proof.
In order to show that𝒳[A]⊆⋃s∈𝒮,|s|≤k≤K(𝒳R[K-k+|s|,h′,s]⊗𝒳[k,h,s]), take x∈𝒳[A]. Moreover, take s∶=x(h+1,h′-1), y∶=0h·s·x(h′,m), y′∶=x(1,h)·s·0m-h′+1, and k∶=|y|. In the following, we prove that y′∈𝒳R[K-k+|s|,h′,s] and y∈𝒳[k,h,s]. Obviously, y⊢(s,h) and y′⊢R(s,h′). For which concerning the number of insertions, it is clear that y satisfies Constraint (12) of Sub[k,h,s], as k=|y|. Moreover, note that |x|≤K, because x∈𝒳[A], and |y′|=|x|-|y|+|s|. Thus, |y′|≤K-k+|s|, and then y′ satisfies Constraint (12) of Sub[K+|s|-k,h′,s]. About the capacity constraints, in order to show that y satisfies them on the knapsacks [h+c+u+1,m], we can apply Observation 2 with a=h+1. Conversely, applying Observation 1 with a=h′-1, we obtain that y′ satisfies the capacity constraint on the knapsacks [1,h′-u-1].
To prove the converse inclusion, takes∈𝒮, k such that |s|≤k≤K, y′∈𝒳R[K-k+|s|,h′,s], and y∈𝒳[k,h,s]. We prove that x∶=y′(1,h)·s·y(h′,s)∈𝒳[A]. Clearly, since |y′|≤K-k+|s| and |y|≤k, we get that |x|=|y′|+|y|-|s|≤K, thus x satisfies Constraint (12). Moreover, since L≥c, it is simple to verify that x satisfies also Constraint (5). Furthermore, exploiting Observation 2 with a=h+1, and Observation 1 with a=h′-1, we get that x satisfies the capacity constraint on all the knapsacks [1,m].Letsopt and kopt be the values of s and k that maximize (24). Moreover, let xopt∈{0,1}m be a best solution for an IKHO instance A. Clearly, the signature sopt represents a piece of xopt, that is, sopt=xopt(h+1,h′-1). In addition, note that kopt determines a distribution of the best solution insertions, that is, |xopt(h+1,m)|≤kopt and |xopt(1,h′-1)|≤K-kopt+|sopt|. If we do not consider the insertions given by the signature sopt, we obtain |xopt(h′,m)|≤kopt-|sopt| and |xopt(1,h)|≤K-kopt, as described in Figure 7.Figure 7
The subdivision on thek dimension. A possible best solution xopt is drawn. The black spots represent the insertions. It is simple to see that the value kopt-|sopt| is a bound for the number of insertions placed at the right of sopt, while K-kopt bounds the number of insertions at the left of the signature.Having fixed theL middle elements of xopt has an important consequence. The radiations of weight starting from the insertions at the left of sopt cannot interfere with the radiations coming from the insertions placed at the right of sopt, as shown in Figure 8. In particular, by (9), the right insertions affect only the range [h′-u,m], while the left insertions interest only the knapsacks [1,h+c+u].Figure 8
The subdivision on thes dimension. The radiations of weight coming from the right knapsacks do not reach those starting from the left knapsacks.Therefore, in order to compute the entire part ofxopt which stands at the right of sopt, it is enough to know sopt, because the checks on the capacity constraints are independent from the insertions at the left of sopt. The same clearly holds also for finding the left piece of xopt. Thus, we subdivided the main problem in two independent subproblems, as follows:(i)
to find the best solution in the knapsacks[h′,m], obeying the capacity constraints over the knapsacks [h′-u,m], having at most kopt-|sopt| insertions and knowing that xopt(h+1,h′-1)=sopt;(ii)
to find the best solution in the knapsacks[1,h], obeying the capacity constraints over the knapsacks [1,h+c+u], having at most K-kopt insertions and knowing that xopt(h+1,h′-1)=sopt.The above-obtained subproblems are solvable as an IKHO instance, by recursively applying (24) with some adjustments. The only significant difference between the main call and the recursive calls is that, in the second ones, when checking the capacity constraints, we have to consider the insertions given by the previously fixed sopt. Indeed, we can simplify this task by progressively updating the vector of capacities b, by subtracting w(sopt,ℓ) for each ℓ∈[1,m]. For each step of recursion, the new vector b will be passed to the input of the lower level subproblems. The solution of each subproblem fixes over xopt a signature sopt, so as to recursively cover xopt with substrings of length L. This is visualized in Figure 9. Finally, note that the base cases for this recursion are the subproblems which involve a number of knapsacks lower than L. In order to compute the best solution for them, we simply list all the feasible solutions and compare the profits.Figure 9
Coveringxopt recursively. An optimal solution xopt is drawn. The black elements are determined by the first call of (24). The more gray knapsacks are determined by the two next levels of calls.


### 5.2. Complexity

As mentioned at the beginning of this section, in the first call (root node of the recursion tree), the computing of (24) takes O(|𝒮|×K) space. The recursive calls occupy geometrically less memory than the first call, as they deal with an halvened number of knapsacks (and with a lower value of K), whence the total memory consumption is of the same order as the memory consumption for the sole first call. Note that, for each step of recursion, once we found kopt and sopt, we can deallocate the matrices opt and optR. Besides these matrices, we need O(m) space for dynamically compose the best solution xopt. Therefore, the new algorithm takes only O(m+[|𝒮|×K]) space.Let us now analyze its time complexity. In the first call, for the computation of (24), the algorithm spends O(m×|𝒮|×K) time to compute the matrices opt and optR, and O(|𝒮|×K) time to pick out the values sopt and kopt. It also spends O(L2) time in order to update the vector b by subtracting the radiations of weight given by sopt. In fact, a signature has width L, and the range of influence of an insertion is c+2u+1=L+1. To give an estimate for the subproblems computation, we need to study how the two terms found, O(L2) and O(m×|𝒮|×K), propagate on the next levels of calls. Moreover, let us write them as α·L2 and β·(m×|𝒮|×K), for some constants α,β.First, note that the recursive calling scheme for (24) can be approximated with a binary tree of height ⌈log2(m)⌉. Indeed, since the calls on an input of L knapsacks are treated as leaf cases, the height of the binary tree corresponds to the first integer n such that L·2n≥m, that is, ⌈log2(m/L)⌉. Moreover, it is simple to find that such a binary tree has O(m/L) nodes. In fact, since for each level i, we have at most 2i nodes, the total number of nodes is (26)∑i=0log⁡2(m/L)2i=1-2log⁡2(m/L)+11-2=1-2⋅(m/L)-1=2⋅mL-1.
Therefore, considering all the calls of (24), for the first term, we obtain αL2·γ(m/L)=O(m×L).Note that, when we call the two children of a node, both the knapsack array dimension and theK dimension are subdivided. In particular, we call the children resolution on two half of the knapsacks array (m/2 and m/2), and taking parameters K′ and K′′ such that K′+K′′≤K. Thus, for each level i, and each node j, the second term of complexity is β×(m/2i)×Kj×|𝒮|, such that ∑jKj≤K. Therefore, for the second term, the complexity for each entire level i, is clearly β×(m/2i)×K×|𝒮|. Moreover, by adding up each level, we get that the total complexity for the second term is
(27)∑i=0log⁡2⁡(m/L)(β×m2i×K×|S|)=βmK|S|×∑i=0log⁡2⁡(m/L)12i≤βmK|S|×2=O(mK|S|).
Since |𝒮|=Sc(L)≥L, the second term O(m×|𝒮|×K) always bounds the first O(m×L). Therefore, the complexity of the nodes computation is O(m×|𝒮|×K).Regarding the computation of the leaf cases, note that we have to find the best feasible piece of solution, for an input of at mostL knapsacks. Since these pieces have length lower than L, and they must obey Constraint (5), they are at most |𝒮|. Moreover, we have to consider the cost of checking the capacity constraints on O(L) knapsacks. Thus, a leaf case can be solved in O(|𝒮|×L) time. Since we have O(m/L) leaf cases, the total cost of the leaf cases is O(m×|𝒮|), that is not higher than the complexity needed for computing the nodes. Therefore, the memory-saving version of the algorithm has time complexity of O(m×|𝒮|×K), which is the same as for the base version.


## 5.1. The Algorithm

In the following, we writex⊢R(s,h) when xh-L-1+j=sj for each j∈[1,L] and xi=0 for each i∈[h,m], that is, when x  ends with the signature s in the knapsacks [h-L,h-1].Given a naturalk≤K, a natural h∈[L+1,m+1], and a signature s, we consider a modified problem SubR[k,h,s] whose solutions are those x∈{0,1}m which obey
(23)x⊢R(s,h),w(x,l)≤bl∀l∈[1,h-u-1],|x|≤k,and(5).
The subproblems SubR[k,h,s] are simply the symmetrical transposition of the subproblems Sub[k,h,s]. The only significant difference is that we check the capacity constraints in the range [1,h-u-1], that is, not symmetrical to the range [h+c+u+1,m]. This dissimilarity is caused by the fact that also the radiations produced by an insertion are not symmetrical too (see (9)).We denote by𝒳R[k,h,s] the space of the feasible solutions to the modified problem SubR[k,h,s]. Moreover, optR[k,h,s] is the maximum profit of a solution in 𝒳R[k,h,s] when 𝒳R[k,h,s] is not empty, and optR[k,h,s]=-∞ when 𝒳R[k,h,s] is empty. Notice that, since the subproblems Sub and SubR are symmetrical, the properties proved for opt hold symmetrically for optR, bringing some adjustments due to the fact that the radiations are not exactly symmetrical. Thus, for computing the matrix optR, we take the same space and time needed for computing the matrix opt, that is, O(|𝒮|×K) space and O(m×|𝒮|×K) time.In the following, let|s| to be the number of insertions in a signature s. For each s∈𝒮, and for h=0,…,m-L, let p(s,h)∶=∑i=1Lsiph+i′. Clearly, this function holds for each knapsack h the profit caused by placing the signature s in the knapsacks [h+1,…,h+L]. Moreover, for α,β=1,…,m, and y∈{0,1}m, let y(α,β) be the substring of y composed by the elements in the range [α,β] (we assume y(α,β) is empty when α<β). Furthermore, for k,k′≤K, for each signature s, for h=0,…,m-L and h′=L+1,…,m-L such that h′-h=L+1, let 𝒳R[k′,h′,s]⊗𝒳[k,h,s]∶={y′(1,h)·s·y(h′,m):y′∈𝒳R[k′,h′,s],y∈𝒳[k,h,s]}. This new operator defines a new space of solutions given by the concatenation of the feasible solutions of two symmetrical subproblems. Notice that the signature s represents the joining point when concatenating the two strings. This situation is represented in Figure 6, which is also useful to visualize the proof of Lemma 6, which represents the main innovation on our algorithm.Figure 6
Joining𝒳R[k′,h′,s] with 𝒳[k,h,s]. The solution y belongs to the space 𝒳[k,h,s], while y′∈𝒳R[k′,h′,s]. Note that the knapsacks [h+c+u+1,m], where y satisfies the capacity constraint, are complementary to the knapsacks [1,h′-u-1], where y′ satisfies that constraint.Lemma 6.
Leth=m/2-L/2-1, and h′=h+L+1.
Then,(24)opt[A]=max⁡s∈S,|s|≤k≤K⁡(optR[K-k+|s|,h′,s]+opt[k,h,s]-p(s,h)).
Indeed,
(25)X[A]=⋃s∈S,|s|≤k≤K(XR[K-k+|s|,h′,s]⊗X[k,h,s]).Proof.
In order to show that𝒳[A]⊆⋃s∈𝒮,|s|≤k≤K(𝒳R[K-k+|s|,h′,s]⊗𝒳[k,h,s]), take x∈𝒳[A]. Moreover, take s∶=x(h+1,h′-1), y∶=0h·s·x(h′,m), y′∶=x(1,h)·s·0m-h′+1, and k∶=|y|. In the following, we prove that y′∈𝒳R[K-k+|s|,h′,s] and y∈𝒳[k,h,s]. Obviously, y⊢(s,h) and y′⊢R(s,h′). For which concerning the number of insertions, it is clear that y satisfies Constraint (12) of Sub[k,h,s], as k=|y|. Moreover, note that |x|≤K, because x∈𝒳[A], and |y′|=|x|-|y|+|s|. Thus, |y′|≤K-k+|s|, and then y′ satisfies Constraint (12) of Sub[K+|s|-k,h′,s]. About the capacity constraints, in order to show that y satisfies them on the knapsacks [h+c+u+1,m], we can apply Observation 2 with a=h+1. Conversely, applying Observation 1 with a=h′-1, we obtain that y′ satisfies the capacity constraint on the knapsacks [1,h′-u-1].
To prove the converse inclusion, takes∈𝒮, k such that |s|≤k≤K, y′∈𝒳R[K-k+|s|,h′,s], and y∈𝒳[k,h,s]. We prove that x∶=y′(1,h)·s·y(h′,s)∈𝒳[A]. Clearly, since |y′|≤K-k+|s| and |y|≤k, we get that |x|=|y′|+|y|-|s|≤K, thus x satisfies Constraint (12). Moreover, since L≥c, it is simple to verify that x satisfies also Constraint (5). Furthermore, exploiting Observation 2 with a=h+1, and Observation 1 with a=h′-1, we get that x satisfies the capacity constraint on all the knapsacks [1,m].Letsopt and kopt be the values of s and k that maximize (24). Moreover, let xopt∈{0,1}m be a best solution for an IKHO instance A. Clearly, the signature sopt represents a piece of xopt, that is, sopt=xopt(h+1,h′-1). In addition, note that kopt determines a distribution of the best solution insertions, that is, |xopt(h+1,m)|≤kopt and |xopt(1,h′-1)|≤K-kopt+|sopt|. If we do not consider the insertions given by the signature sopt, we obtain |xopt(h′,m)|≤kopt-|sopt| and |xopt(1,h)|≤K-kopt, as described in Figure 7.Figure 7
The subdivision on thek dimension. A possible best solution xopt is drawn. The black spots represent the insertions. It is simple to see that the value kopt-|sopt| is a bound for the number of insertions placed at the right of sopt, while K-kopt bounds the number of insertions at the left of the signature.Having fixed theL middle elements of xopt has an important consequence. The radiations of weight starting from the insertions at the left of sopt cannot interfere with the radiations coming from the insertions placed at the right of sopt, as shown in Figure 8. In particular, by (9), the right insertions affect only the range [h′-u,m], while the left insertions interest only the knapsacks [1,h+c+u].Figure 8
The subdivision on thes dimension. The radiations of weight coming from the right knapsacks do not reach those starting from the left knapsacks.Therefore, in order to compute the entire part ofxopt which stands at the right of sopt, it is enough to know sopt, because the checks on the capacity constraints are independent from the insertions at the left of sopt. The same clearly holds also for finding the left piece of xopt. Thus, we subdivided the main problem in two independent subproblems, as follows:(i)
to find the best solution in the knapsacks[h′,m], obeying the capacity constraints over the knapsacks [h′-u,m], having at most kopt-|sopt| insertions and knowing that xopt(h+1,h′-1)=sopt;(ii)
to find the best solution in the knapsacks[1,h], obeying the capacity constraints over the knapsacks [1,h+c+u], having at most K-kopt insertions and knowing that xopt(h+1,h′-1)=sopt.The above-obtained subproblems are solvable as an IKHO instance, by recursively applying (24) with some adjustments. The only significant difference between the main call and the recursive calls is that, in the second ones, when checking the capacity constraints, we have to consider the insertions given by the previously fixed sopt. Indeed, we can simplify this task by progressively updating the vector of capacities b, by subtracting w(sopt,ℓ) for each ℓ∈[1,m]. For each step of recursion, the new vector b will be passed to the input of the lower level subproblems. The solution of each subproblem fixes over xopt a signature sopt, so as to recursively cover xopt with substrings of length L. This is visualized in Figure 9. Finally, note that the base cases for this recursion are the subproblems which involve a number of knapsacks lower than L. In order to compute the best solution for them, we simply list all the feasible solutions and compare the profits.Figure 9
Coveringxopt recursively. An optimal solution xopt is drawn. The black elements are determined by the first call of (24). The more gray knapsacks are determined by the two next levels of calls.


## 5.2. Complexity

As mentioned at the beginning of this section, in the first call (root node of the recursion tree), the computing of (24) takes O(|𝒮|×K) space. The recursive calls occupy geometrically less memory than the first call, as they deal with an halvened number of knapsacks (and with a lower value of K), whence the total memory consumption is of the same order as the memory consumption for the sole first call. Note that, for each step of recursion, once we found kopt and sopt, we can deallocate the matrices opt and optR. Besides these matrices, we need O(m) space for dynamically compose the best solution xopt. Therefore, the new algorithm takes only O(m+[|𝒮|×K]) space.Let us now analyze its time complexity. In the first call, for the computation of (24), the algorithm spends O(m×|𝒮|×K) time to compute the matrices opt and optR, and O(|𝒮|×K) time to pick out the values sopt and kopt. It also spends O(L2) time in order to update the vector b by subtracting the radiations of weight given by sopt. In fact, a signature has width L, and the range of influence of an insertion is c+2u+1=L+1. To give an estimate for the subproblems computation, we need to study how the two terms found, O(L2) and O(m×|𝒮|×K), propagate on the next levels of calls. Moreover, let us write them as α·L2 and β·(m×|𝒮|×K), for some constants α,β.First, note that the recursive calling scheme for (24) can be approximated with a binary tree of height ⌈log2(m)⌉. Indeed, since the calls on an input of L knapsacks are treated as leaf cases, the height of the binary tree corresponds to the first integer n such that L·2n≥m, that is, ⌈log2(m/L)⌉. Moreover, it is simple to find that such a binary tree has O(m/L) nodes. In fact, since for each level i, we have at most 2i nodes, the total number of nodes is (26)∑i=0log⁡2(m/L)2i=1-2log⁡2(m/L)+11-2=1-2⋅(m/L)-1=2⋅mL-1.
Therefore, considering all the calls of (24), for the first term, we obtain αL2·γ(m/L)=O(m×L).Note that, when we call the two children of a node, both the knapsack array dimension and theK dimension are subdivided. In particular, we call the children resolution on two half of the knapsacks array (m/2 and m/2), and taking parameters K′ and K′′ such that K′+K′′≤K. Thus, for each level i, and each node j, the second term of complexity is β×(m/2i)×Kj×|𝒮|, such that ∑jKj≤K. Therefore, for the second term, the complexity for each entire level i, is clearly β×(m/2i)×K×|𝒮|. Moreover, by adding up each level, we get that the total complexity for the second term is
(27)∑i=0log⁡2⁡(m/L)(β×m2i×K×|S|)=βmK|S|×∑i=0log⁡2⁡(m/L)12i≤βmK|S|×2=O(mK|S|).
Since |𝒮|=Sc(L)≥L, the second term O(m×|𝒮|×K) always bounds the first O(m×L). Therefore, the complexity of the nodes computation is O(m×|𝒮|×K).Regarding the computation of the leaf cases, note that we have to find the best feasible piece of solution, for an input of at mostL knapsacks. Since these pieces have length lower than L, and they must obey Constraint (5), they are at most |𝒮|. Moreover, we have to consider the cost of checking the capacity constraints on O(L) knapsacks. Thus, a leaf case can be solved in O(|𝒮|×L) time. Since we have O(m/L) leaf cases, the total cost of the leaf cases is O(m×|𝒮|), that is not higher than the complexity needed for computing the nodes. Therefore, the memory-saving version of the algorithm has time complexity of O(m×|𝒮|×K), which is the same as for the base version.


## 6. Conclusions

In [3], Aho exhibited a few classes of polynomial instances for the IKHO problem, motivated by the fact that IKHO is NP-complete [1] and APX-hard [2]. The most important class of instances identified by Aho is represented by the instances where c+2u+1=O(log(mα)), for a constant α. Throughout Sections 3 and 4, we identified a new and wide class of instances allowing for a polynomial time algorithm. We achieved this by showing how to build a dynamic programming algorithm which executes in time of O(cr×m×K) and takes space of O(cr×m×K) for the instances where (c+2u)/c is bounded by a constant r. These results represent a significant improvement to the understanding of the IKHO problem and more in general for the Interactive Knapsacks problems to which IKHO belongs and that are extensively presented by Aho in [4]. Note that our results imply Aho's results for IKHO, as shown in Section 2.2. In Section 5, we also exploited Hirschberg's approach in order to create a memory saving version of our algorithm which decreases the space complexity to O(cr×K+m) without increasing the time complexity.Extensive experimental evaluations have been performed on the c++ implementations of both algorithms, confirming the complexity estimates given in Sections4 and 5. In addition, these experiments pointed out that, despite the heavy constants introduced in the time complexity bound of the memory saving version, the last version of the algorithm is often faster than the base version in the practice. This is mainly due to the fact that the higher memory usage of the base version brings the operative system to allocate data in the slowest memory devices like the RAM and the hard disk, instead of using the CPU cache.



---

*Source: 859820-2012-04-08.xml*