On the job rotation problem



of these disjoint subgraphs, and it is not possible to have a cycle in D(A) with
arcs corresponding to elements from more than one of the matrices
A1 , . . . , Ap.

We now show how to solve JRP (A) for A = blockdiag(A1 , A2, . . . , Ap) in
polynomial time, as long as we can solve
JRP (Aj ) in polynomial time, for
j = 1, . . . , p. This is shown in an algorithm called JRPBLOCKDIAG (see
Figure 2).

Let n(j) be the order of Aj , j = 1, . . . , p. Assume that we have solved
JRP (Aj). This may have been done in polynomial time if Aj is one of the
special types of matrix previously mentioned in this paper.

So for j = 1, . . . p and r = 1, . . . , k we are able to find δr (Aj ) and also a
principal submatrix
Bjr (Aj)r (where (Aj)r is the set of all r × r principal
submatrices of
Aj ) and permutation πjr ap(Bj r) such that w(Bjr , πjr) =
δr(Aj).

Let Dj = D(Aj ). For each block Aj , we have the following information: For
r = 1, . . . , k, the permutation πjr in Dj gives cycles of total length r and total
weight
δr (Aj).

We will use S , a set of pairs to tell us which submatrix to select and which
elements from within it to select. We do this by assigning pairs (
j, r) to S. A
pair (
j, r) tells us that by choosing Bjr and πjr we select a total of r elements
from
Bjr and give a total sum of δr (Aj ).

There are p stages to the algorithm. At each stage information is collected
and then stored within a set of triples called
Mj . Each triple has the form
(
S, w, k), where S is as described above, w is the total weight of elements selected
by using the information in
S , and k is the total number of elements selected
by using the information in
S .

M0 is set to {(0,0, 0)} at Stage 0. For j = 1,... ,p, at Stage j, the infor-
mation found from
Aj (i.e. δ1 (Aj), δ2 (Aj), . . . , δn(j) (Aj)) and the information
from Stage
j - 1 (i.e. Mj-1) is combined to produce Mj . We start by copying
all triples from
Mj-1 to Mj. Next, if we can find a triple (S, w, k) (of the form
described above) by combining the information found from
Aj and Mj-1 that
is not in
Mj , then we add (S, w, k) to Mj . Otherwise, if w is larger than the
second coordinate of any triple in
Mj having third component equal to k, then
we replace that triple with (
S, w, k) in Mj .

We now give the algorithm, called JRPBLOCKDIAG, and then discuss the
correctness and complexity of this algorithm.

15



More intriguing information

1. The name is absent
2. Valuing Access to our Public Lands: A Unique Public Good Pricing Experiment
3. Revisiting The Bell Curve Debate Regarding the Effects of Cognitive Ability on Wages
4. The Advantage of Cooperatives under Asymmetric Cost Information
5. How much do Educational Outcomes Matter in OECD Countries?
6. Quality practices, priorities and performance: an international study
7. The name is absent
8. Private tutoring at transition points in the English education system: its nature, extent and purpose
9. Quelles politiques de développement durable au Mali et à Madagascar ?
10. The name is absent