On the job rotation problem



time. The whole of Step 2 is carried out for j = 1, . . . , p. It is easily seen that
Step 3 can be done in
O(n2) time. So algorithm JRPBLOCKDIAG runs in time
Pp =1 O(n(j))t + PpO(n)O(n(j)) + O(n2) = O(n(n + t)).                □

Corollary 22. If in Theorem 21, t is polynomial in n, that is, if JRP (Ai, k0)
can be solved in polynomial time, for all i = 1, . . . , p and k
0 = 1, . . . , k, then for
a block diagonal matrix A, JRP(A) can be solved in polynomial time.

Any matrix that can be obtained by permuting the rows and/or columns of
the matrix containing zeros on the main diagonal and
-∞ elsewhere, will be
called a
permutation matrix. Any matrix that can be obtained by permuting the
rows and/or columns of a matrix containing finite entries on the main diagonal
and
-∞ elsewhere, will be called a generalized permutation matrix. It is known
[8] that JRP (A) can be solved in O(n
2 ) time, for a permutation matrix A.
With the same time complexity, this is also true for generalized permutation
matrices:

Corollary 23. For any generalized permutation matrix A Rn×n, JRP(A)
can be solved in
O(n2 ) time.

Proof. Generalized permutation matrices are a special type of block diagonal
matrix. Each block contains only one cycle, therefore we can solve JRP for each
block in linear time, and hence use Theorem 21 to give the result.          □

Any element of a matrix that does not lie on a finite cycle may be set to -∞
without affecting δk for any k N . Hence if B is in Frobenius normal form,
then we may set all elements of off-diagonal blocks in
B to -∞. Therefore if
we define
Ci = Bii, for i = 1, . . . , p, i.e.

C = blockdiag(C1, C2,..., Cp),

then we have δk (C) = δk (A) for all k N . We have derived the following:

Theorem 24. For any A Rn×n, if we can solve JRP for all diagonal blocks of
the Frobenius normal form of
A in polynomial time, then we can solve JRP(A)
in polynomial time (by converting it to a block diagonal matrix and using the
JRPBLOCKDIAG algorithm of Figure 2).

18



More intriguing information

1. Testing the Information Matrix Equality with Robust Estimators
2. Naïve Bayes vs. Decision Trees vs. Neural Networks in the Classification of Training Web Pages
3. Structural Conservation Practices in U.S. Corn Production: Evidence on Environmental Stewardship by Program Participants and Non-Participants
4. Financial Market Volatility and Primary Placements
5. Natural hazard mitigation in Southern California
6. The name is absent
7. Qualifying Recital: Lisa Carol Hardaway, flute
8. Job quality and labour market performance
9. Natural Resources: Curse or Blessing?
10. Crime as a Social Cost of Poverty and Inequality: A Review Focusing on Developing Countries
11. The name is absent
12. The name is absent
13. Word searches: on the use of verbal and non-verbal resources during classroom talk
14. An Interview with Thomas J. Sargent
15. Automatic Dream Sentiment Analysis
16. Iconic memory or icon?
17. AGRIBUSINESS EXECUTIVE EDUCATION AND KNOWLEDGE EXCHANGE: NEW MECHANISMS OF KNOWLEDGE MANAGEMENT INVOLVING THE UNIVERSITY, PRIVATE FIRM STAKEHOLDERS AND PUBLIC SECTOR
18. The Challenge of Urban Regeneration in Deprived European Neighbourhoods - a Partnership Approach
19. The name is absent
20. The name is absent