On the job rotation problem

2. If S ⊆ {1, . . . , p} × {1, . . . , n}, and s = k ≤ n, then in Step 3 of the
(i,s)∈S

algorithm, ∃(S⁰, w⁰, k) ∈ Mj where w ≤ w⁰.

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, ∃(S⁰⁰, w⁰⁰, k) ∈ Mj, with w⁰ ≤ w⁰⁰. By 1(d),
we see that S⁰ = S and w⁰ = w, therefore w⁰ ≤ 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(A₁ ,A2,...,Ap) ∈ Rn×n and we can solve
JRP (A_i, 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

<<   14   15   16   17   18   19   20   >>

More intriguing information