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(n2(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 max
kN δk (A) = m(A0) where A0 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

×n


Rj


Let T = {0, -∞} and A Tn×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 Tn×n is equivalent to deciding whether there exist PND cycles in D(A)
covering exactly
k nodes.

Theorem 3. If A Tn×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



More intriguing information

1. Political Rents, Promotion Incentives, and Support for a Non-Democratic Regime
2. On the Relation between Robust and Bayesian Decision Making
3. TOWARDS THE ZERO ACCIDENT GOAL: ASSISTING THE FIRST OFFICER MONITOR AND CHALLENGE CAPTAIN ERRORS
4. The name is absent
5. Regional differentiation in the Russian federation: A cluster-based typification
6. Langfristige Wachstumsaussichten der ukrainischen Wirtschaft : Potenziale und Barrieren
7. Applications of Evolutionary Economic Geography
8. The Institutional Determinants of Bilateral Trade Patterns
9. The name is absent
10. The name is absent