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, (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



More intriguing information

1. Institutions, Social Norms, and Bargaining Power: An Analysis of Individual Leisure Time in Couple Households
2. Income Taxation when Markets are Incomplete
3. Wirkt eine Preisregulierung nur auf den Preis?: Anmerkungen zu den Wirkungen einer Preisregulierung auf das Werbevolumen
4. A dynamic approach to the tendency of industries to cluster
5. Om Økonomi, matematik og videnskabelighed - et bud på provokation
6. The name is absent
7. Ability grouping in the secondary school: attitudes of teachers of practically based subjects
8. BUSINESS SUCCESS: WHAT FACTORS REALLY MATTER?
9. The name is absent
10. Evaluating the Success of the School Commodity Food Program