On the job rotation problem

Corollary 9. Let A ∈ T^n×n be a symmetric matrix, σ1 , σ2 , . . . , σt be a collec-
tion of PND cycles in D(A) covering kmax or kmax - 1 nodes, with at least one
having length koddmin. Then we can decide whether δk (A) is 0 or -∞ for all k
in linear time, after finding kmax and koddmin .

Proof. The result follows from Corollary 4 and Theorem 8.

Theorem 10. If A ∈ T^n×n is a symmetric matrix, then δk (A) = 0 for all odd

k ∈ {k_oddmin, . . . , k_max

Proof. As δk_max = 0, there exist PND cycles σ1, σ2, . . . , σt in D(A) that cover
kmax nodes. There exists a cycle σ in D(A) of length koddmin.

Delete all nodes in V (σ) from σ₁, σ₂, . . . , σ_t, as well as incident arcs. As
the cycles were PND and each node was incident to precisely two arcs, up
to 2koddmin arcs have been deleted. Therefore this leaves a total of at least
kmax - 2koddmin arcs within the remaining PND cycles and paths that have
arisen from deleting the arcs from the cycles. Split any paths into 2-cycles.
We now have PND cycles in D(A) covering at least kmax - 2koddmin arcs, and
therefore at least kmax - 2koddmin nodes, none of which are nodes on σ.

Therefore, by Corollary 4, for all even i ≤ kmax - 2koddmin , there exist PND
cycles σ₁⁰ , σ₂⁰ , . . . , σ_t⁰0 in D(A) covering i nodes, but none on σ. So for all even
i ≤ kmax - 2koddmin, we have PND cycles σ₁⁰ , σ₂⁰ , . . . , σ_t⁰0 and σ in D(A) which
cover i + k_oddmin nodes. Hence the result.                                 □

Remark. Note that {^koddmin^, ∙ ∙ ∙ ^{, k}max koddmin} = ^ ^ ⇒ ^koddmin ≤   2 .

Corollary 11. Let A ∈ T^n×n be a symmetric matrix, with PND cycles in
D(A) covering kmax or kmax - 1 nodes, one having odd length of at most
k_max - k_oddmin . Then we can decide whether δ_k (A) is 0 or -∞ for all k in
linear time, after finding kmax and koddmin .

Proof. The result follows from Corollary 4, Theorem 8 and Theorem 10.    □

Corollary 12. Let A ∈ T^n×n be a symmetric matrix, with PND cycles in D(A)
covering kmax or kmax - 1 nodes, two having odd length. Then we can decide
whether δk (A) is 0 or -∞ for all k in linear time, after finding kmax .

Proof. The result follows from Corollary 11 and the fact that the length of at
least one of the odd cycles is at most k^m2^ax ≤ k_max — k_oddmin.               □

10

<<   <   7   8   9   10   11   12   13   >   >>