On the job rotation problem

alternate arcs from σ, starting with an incident arc to node v and ending with
the other incident arc to node v, and adding counterarcs (j, i) for each (i, j)
that remains from σ, resulting in a collection of ^p-1 PND cycles in D (A) that
cover p - 1 nodes from V (σ), with node v not being covered. We define splitting
a path with p arcs as deleting alternate arcs on that path starting from the
second arc and adding counterarcs to the remaining arcs, to form a collection
of p 2-cycles if p was even, or ^p++1 2-cycles if p was odd.

The task of finding kmax for a general matrix can be solved in O(n³) time
[8], however we can do better for symmetric matrices:

Theorem 2. ([7]) The task of finding k_max for a symmetric matrix A ∈ Rn×n is
equivalent to the maximum cardinality matching problem in a bipartite graph
with 2n nodes and can therefore be solved in O(n²∙⁵/ʌ/log n) time.

Proof. Let B(A) be the bipartite graph with the bipartition (U, V ), where U =
{u₁, ..., u_n}, V = {v₁, ..., v_n} and set of arcs {u_ivj; a_ij > -∞}.

Let M be a matching of maximum cardinality in B(A), |M| = m. Obviously
kmax ≤ m because if k = kmax then there are k finite entries in A, no two in
the same row or column, say a_irπ(_ir), r = 1, ..., k, and so there is a matching of
cardinality k in B(A), namely, {u_ir v_π(_ir) ; r = 1, ..., k}.

We now prove kmax ≥ m. The set of arcs H = {(i, j); uivj ∈ M} in D(A)
consists of directed PND elementary paths or cycles, since both the outdegree
and indegree of each node in (N, H) is at most one. We will call a path proper
if it is not a cycle.

Construct from H another set H⁰ as follows (see Figure 1): If all paths in
H are cycles then set H⁰ = H. Now suppose that at least one proper path
exists. Splitting every proper path in (N, H), we obtain a digraph (N, H⁰)
which consists of original cycles in (N, H ) and a number of cycles of length 2.
All cycles in (N, H⁰) are PND.

Each set of PND cycles in D(A) determines a matching in B(A) whose
cardinality is equal to the total number of arcs of these cycles. Thus none of
the proper paths in (N, H) could have been of odd length, say s, as otherwise
the total number of arcs on cycles constructed from this path would be s + 1, a
contradiction with the maximality of M . Hence |H⁰ | = m and thus kmax ≥ m.

The complexity statement now follows from [3].                         □

<<   2   3   4   5   6   7   8   >>

More intriguing information