2. If S ⊆ {1, . . . , p} × {1, . . . , n}, and s = k ≤ n, then in Step 3 of the
(i,s)∈S
algorithm, ∃(S0, w0, k) ∈ Mj where w ≤ w0.
Proof. Statements 1(a)-1(c) are proved by induction on j, and hold automat-
ically for j = 0. For j > 0, assume (S, w, k) ∈ Mj . We have two cases to
consider:
Case 1: If @(j, r) ∈ S, then (S, w, k) ∈ Mj-1, so 1(a)-1(c) follow by induction.
Case 2: If ∃(j,r) ∈ S, then (S-{(j,r)},w-δr(Aj),k-r) ∈ Mj-1. Note that
r ≤ n, as the third coordinate of this lies between 0 and n - r. So again
1(a)-1(c) follow by induction.
To prove 1(d), we use the fact that each element of Mj has a unique third
component due to the way Step 2(c) of the algorithm was constructed.
To prove 2, we use induction on max h.
(h,s)∈S
To prove 1(e), note that by 2, ∃(S00, w00, k) ∈ Mj, with w0 ≤ w00. By 1(d),
we see that S0 = S and w0 = w, therefore w0 ≤ w, and 1(e) follows. □
From part 2 of Lemma 20, we see that if we have an S ⊆ {1, . . . , p} ×
{1,..., k} with P s = k and P δs(Ai) = w, then 3(S*,w*,k) ∈ Mp
(i,s)∈S (i,s)∈S
(which gives at least as much total weight w* as w does). Then from part 1(e)
of Lemma 20, we see that if (S*,w*,k) ∈ Mp, then no other first coordinate
satisfying ɪɪ s = k will provide a bigger total weight than w*. Selecting
(i,s)∈S
elements of A that correspond to the (i, πj r (i)) entry of Bjr for all i = 1, . . . , r
and all (j, r) ∈ S and adding them up will give w*, which is the highest possible
value, so w = δk (A).
Theorem 21. If A = blockdiag(A1 ,A2,...,Ap) ∈ Rn×n and we can solve
JRP (Ai, k) in O(t) time, for all i = 1, . . . , p and k = 1, . . . , n, then we can solve
JRP (A) in O(n(n + t)) time.
Proof. Correctness follows from Lemma 20. For the time bound, notice that
the size of each set Mj-1 is no greater than n, because there is at most one
element in Mj-1 with the same third component (by 1(d) of Lemma 20). Each
update operation of Step 2(c) can be done in constant time for each r and each
Mj-1, and must be repeated for all O(n) elements of Mj-1 and O(n(j)) times
for the r loop. Steps 1, and 2(b) require one operation each so can be performed
in constant time. Assume that for each r, Step 2(a) can be performed in O(t)
17