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(n²) time. So algorithm JRPBLOCKDIAG runs in time
Pp =1 O(n(j))t + Pp=ι O(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 (A_i, k⁰)
can be solved in polynomial time, for all i = 1, . . . , p and k⁰ = 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² ) 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×ⁿ, JRP(A)
can be solved in O(n² ) 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×ⁿ, 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

<<   15   16   17   18   19   20   >>

More intriguing information