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 @(S0, w0, l + r) ∈ Mj, then add (S ∪ {(j, r)}, w + δr (Aj), l + r)
to Mj .
ii. If ∃(S0, w0, l + r) ∈ Mj and w0 < w + δr (Aj ), then remove
(S0, w0, 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, πjr (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 (S0 , w0 , k) ∈ Mj , then S0 = S and w0 = w,
(e) If S0 ⊆ {1,...,p} × {1,...,n}, w0 = P δs(Ai) and P s = k
(i,s)∈S0 (i,s)∈S0
then w0 ≤ w.
16
More intriguing information
1. The name is absent2. AGRIBUSINESS EXECUTIVE EDUCATION AND KNOWLEDGE EXCHANGE: NEW MECHANISMS OF KNOWLEDGE MANAGEMENT INVOLVING THE UNIVERSITY, PRIVATE FIRM STAKEHOLDERS AND PUBLIC SECTOR
3. Barriers and Limitations in the Development of Industrial Innovation in the Region
4. DEMAND FOR MEAT AND FISH PRODUCTS IN KOREA
5. MULTIPLE COMPARISONS WITH THE BEST: BAYESIAN PRECISION MEASURES OF EFFICIENCY RANKINGS
6. The name is absent
7. A Theoretical Growth Model for Ireland
8. The value-added of primary schools: what is it really measuring?
9. A Rare Case Of Fallopian Tube Cancer
10. The name is absent