On the job rotation problem

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

δ_k (A) = max m(B),
^k        B∈Pk(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

-∞, δ₂ = 8, δ₃ = 13, and δ₄ = -∞.

If A = (a_ij) ∈ 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 (τ) = {i₁ , i₂, . . . , i_p}. For a digraph D, we say paths τ₁, τ₂, . . . , τ_s in D are
pairwise node disjoint (PND) if V(τ_i) ∩ V(Tj) = 0 for i, j = 1,..., s,i = j.

For A ∈ Rⁿ×ⁿ, we define k_max(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 ∈ Rⁿ×ⁿ 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

<<   1   2   3   4   5   6   7   >>

More intriguing information