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. 09-01 "Resources, Rules and International Political Economy: The Politics of Development in the WTO"
3. The name is absent
4. Firm Closure, Financial Losses and the Consequences for an Entrepreneurial Restart
5. Social Balance Theory
6. The name is absent
7. Bird’s Eye View to Indonesian Mass Conflict Revisiting the Fact of Self-Organized Criticality
8. IMPLICATIONS OF CHANGING AID PROGRAMS TO U.S. AGRICULTURE
9. The name is absent
10. The name is absent
11. Großhandel: Steigende Umsätze und schwungvolle Investitionsdynamik
12. The Macroeconomic Determinants of Volatility in Precious Metals Markets
13. The name is absent
14. News Not Noise: Socially Aware Information Filtering
15. A Theoretical Growth Model for Ireland
16. Keynesian Dynamics and the Wage-Price Spiral:Estimating a Baseline Disequilibrium Approach
17. Sex-gender-sexuality: how sex, gender, and sexuality constellations are constituted in secondary schools
18. Improvements in medical care and technology and reductions in traffic-related fatalities in Great Britain
19. The name is absent
20. The name is absent