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. Growth and Technological Leadership in US Industries: A Spatial Econometric Analysis at the State Level, 1963-1997
2. The name is absent
3. Nietzsche, immortality, singularity and eternal recurrence1
4. Studies on association of arbuscular mycorrhizal fungi with gluconacetobacter diazotrophicus and its effect on improvement of sorghum bicolor (L.)
5. The name is absent
6. Towards Learning Affective Body Gesture
7. Regional dynamics in mountain areas and the need for integrated policies
8. The Composition of Government Spending and the Real Exchange Rate
9. Inflation Targeting and Nonlinear Policy Rules: The Case of Asymmetric Preferences (new title: The Fed's monetary policy rule and U.S. inflation: The case of asymmetric preferences)
10. Implementation of a 3GPP LTE Turbo Decoder Accelerator on GPU
11. Globalization, Redistribution, and the Composition of Public Education Expenditures
12. The name is absent
13. Federal Tax-Transfer Policy and Intergovernmental Pre-Commitment
14. Improvements in medical care and technology and reductions in traffic-related fatalities in Great Britain
15. The name is absent
16. The name is absent
17. The name is absent
18. Structural Breakpoints in Volatility in International Markets
19. The name is absent
20. La mobilité de la main-d'œuvre en Europe : le rôle des caractéristiques individuelles et de l'hétérogénéité entre pays