On the job rotation problem

algebra as defined in [12]. Max-algebra is the analogue of linear algebra in
which the conventional operations of addition and multiplication are replaced
by φ and φ defined as follows: a φ b = max(a, b) and a φ b = a + b for
a,b ∈ R := R U {-∞}. An account on algebraic properties in max-algebra
can be found in [11] and [13]. Note that in recent years max-algebra has been
investigated under the name ”tropical algebra” in a number of papers, see for
instance [14].

An O(n²(m + n log n)) algorithm is known [4] for finding so called essential
terms of the max-algebraic characteristic polynomial of an n × n matrix where
m is the number of finite entries of A. The algorithm presented in [4] does
not explicitly produce the corresponding k × k principal submatrix but this can
easily be identified from the data produced by the algorithm. It then follows
that this method solves JRP (A, k) for all k = 1, . . . , n, when all terms are
essential or, equivalently when the sequence δ1, . . . , δn is concave [13]. Note
that the complexity bound has recently been improved to O(n(m + n log n))
steps [15].

Max-algebraic theory provides various other information for the job rotation
problem, one of them being that maxk∈N δk (A) = m(A⁰) where A⁰ is obtained
from A after replacing all negative diagonal entries by 0. The corresponding
principal submatrix can also be easily identified.

3 JRP for special symmetric matrices over {0, -∞}

In this section we show that JRP (A, k), for a symmetric matrix A over {0, -∞},
and k even, can be solved in O(1) time, after finding kmax . We also describe
some cases when this is true for odd values of k. These results can immediately

be applied to the question of finiteness of δ_k (A) for symmetric matrices A ∈

Let T = {0, -∞} and A ∈ T^n×n. Then for all k, the unique finite value
for δk (A) is 0. Also, δk (A) = 0 if and only if there exist PND cycles in D(A)
covering a total of k nodes. Hence, deciding if δk (A) = 0 for some matrix
A ∈ T^n×n is equivalent to deciding whether there exist PND cycles in D(A)
covering exactly k nodes.

Theorem 3. If A ∈ T^n×n is a symmetric matrix and δl (A) = 0 for some l ∈ N ,
then δk (A) = 0 for all even k ≤ l, and δk (A) = 0 for all k = l - r, . . . , l, where r
is the number of odd cycles in a collection of PND cycles in D(A) that cover l

<<   4   5   6   7   8   9   10   >>

More intriguing information