On the job rotation problem

Algorithm JRPBLOCKDIAG

Input: A = blockdiag(A 1, A2,..., Ap) ∈ Rn×n.

Output: For k = 1, . . . , n, δ_k (A), and if δ_k (A) is finite, then also k independent
entries of a k × k principal submatrix of A whose total is δk (A).

1. Set M0 = {(0,0, 0)}

2. For j = 1 to p :

(a) For r = 1 to n(j ) :

i. Find δr(Aj).

ii. Find Bjr ∈ (Aj )r and πjr ∈ ap(Bj r) such that w(Bjr, πjr) =
δr(Aj).

(b) Set Mj = Mj_-1

(c) For each element (S, w, l) ∈ Mj-1 :

j

For each r = 1 to min(   n(t) - l, n(j)) with δr (Aj ) finite :

t=1

i. If @(S⁰, w⁰, l + r) ∈ Mj, then add (S ∪ {(j, r)}, w + δr (Aj), l + r)
to Mj .

ii. If ∃(S⁰, w⁰, l + r) ∈ Mj and w⁰ < w + δr (Aj ), then remove
(S⁰, w⁰, l + r) from Mj and add (S ∪ {(j, r)}, w + δ_r (Aj), l + r) to
Mj.

3. For k = 1 to n :

If ∃(S, w, k) ∈ Mp, then return δk (A) = w, and for i = 1, . . . , r and all
(j, r) ∈ S, return the element of A that corresponds to the (i, πj_r (i)) entry
of Bjr. Else return δk (A) = -∞.

Figure 2: An algorithm for solving JRP for block diagonal matrices.

Lemma 20.

1. If (S, w, k) ∈ Mj in Step 3 of the algorithm, then

(a) S ⊆ {1, . . . , p} × {1, . . . , n},

(b) ^P δs(Ai) = w,

(i,s)∈S

(c) ^P s = k,

(i,s)∈S

(d) If (S⁰ , w⁰ , k) ∈ Mj , then S⁰ = S and w⁰ = w,

(e) If S⁰ ⊆ {1,...,p} × {1,...,n}, w⁰ = ^P δs(Ai) and ^P s = k

(i,s)∈S⁰                    (i,s)∈S⁰

then w⁰ ≤ w.

16

<<   13   14   15   16   17   18   19   >>

More intriguing information