On the job rotation problem



Let us denote for k = 1, . . . , n

δk (A) = max m(B),
k        BPk(A)

where Pk(A) is the set of all principal submatrices of A of order k. For sim-
plicity we often write just
δk instead of δk (A). Clearly, δn = m(A) and δ1 =
max(
a11, a22, . . . , ann). Note that δk = -∞ if m(B) = -∞ for all B Pk (A).

Thus JRP(A, k) (k = 1, ..., n) is the problem of finding a matrix B Pk (A)
such that

δk(A) = m(B).

Example 1. Let

A=


-∞


-∞


-∞


1  -∞  0


54


-∞


-∞  6


-∞ -∞


Then it is easily seen that δ1


-∞, δ2 = 8, δ3 = 13, and δ4 = -∞.

If A = (aij) Rn×n then we denote by D(A) the digraph whose set of
nodes is
N and arc set is {(i, j); aij > -∞}. For a path τ = (i1 , i2, . . . , ip), let
V (τ) = {i1 , i2, . . . , ip}. For a digraph D, we say paths τ1, τ2, . . . , τs in D are
pairwise node disjoint (PND) if V(τi) ∩ V(Tj) = 0 for i, j = 1,..., s,i = j.

For A Rn×n, we define kmax(A) or just kmax as

max{k N; δk(A) > -∞}.

Since every permutation is a product of cyclic permutations, kmax (A) is the
biggest number of nodes in
D(A) that can be covered by PND cycles in D(A).
Note that we are not using the word ”elementary” in connection with cycles as
all cycles in this paper are elementary.

Let A Rn×n be a symmetric matrix and σ be an arbitrary cycle of length
p in D(A). By symmetry, for each arc (i, j) in D(A), (j, i) is also an arc
(”counterarc”). If
p is even, we define the operation of splitting σ as removing
alternate arcs from
σ, and adding counterarcs (j, i) for each (i, j) that remains
from
σ, resulting in a collection of 2 PND cycles in D(A) that cover all p nodes
from
V (σ). If σ is a loop, we define the operation of splitting σ as removing
the arc. If
p ≥ 3 is odd, we define the operation of splitting σ - v as removing



More intriguing information

1. New urban settlements in Belarus: some trends and changes
2. MICROWORLDS BASED ON LINEAR EQUATION SYSTEMS: A NEW APPROACH TO COMPLEX PROBLEM SOLVING AND EXPERIMENTAL RESULTS
3. Sustainability of economic development and governance patterns in water management - an overview on the reorganisation of public utilities in Campania, Italy, under EU Framework Directive in the field of water policy (2000/60/CE)
4. Macro-regional evaluation of the Structural Funds using the HERMIN modelling framework
5. The name is absent
6. The name is absent
7. Education and Development: The Issues and the Evidence
8. The name is absent
9. AN ECONOMIC EVALUATION OF COTTON AND PEANUT RESEARCH IN SOUTHEASTERN UNITED STATES
10. Government spending composition, technical change and wage inequality