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(n3) time
[8], however we can do better for symmetric matrices:

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

Proof. Let B(A) be the bipartite graph with the bipartition (U, V ), where U =
{u1, ..., un}, V = {v1, ..., vn} and set of arcs {uivj; aij > -∞}.

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
airπ(ir), r = 1, ..., k, and so there is a matching of
cardinality
k in B(A), namely, {uir 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 H0 as follows (see Figure 1): If all paths in
H are cycles then set H0 = H. Now suppose that at least one proper path
exists. Splitting every proper path in (
N, H), we obtain a digraph (N, H0)
which consists of original cycles in (
N, H ) and a number of cycles of length 2.
All cycles in (
N, H0) 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 |H0 | = m and thus kmax ≥ m.

The complexity statement now follows from [3].                         □



More intriguing information

1. The name is absent
2. The name is absent
3. Unemployment in an Interdependent World
4. The Variable-Rate Decision for Multiple Inputs with Multiple Management Zones
5. Perfect Regular Equilibrium
6. The name is absent
7. ENERGY-RELATED INPUT DEMAND BY CROP PRODUCERS
8. The name is absent
9. Recognizability of Individual Creative Style Within and Across Domains: Preliminary Studies
10. TOWARD CULTURAL ONCOLOGY: THE EVOLUTIONARY INFORMATION DYNAMICS OF CANCER
11. Testing Gribat´s Law Across Regions. Evidence from Spain.
12. Intertemporal Risk Management Decisions of Farmers under Preference, Market, and Policy Dynamics
13. The name is absent
14. Firm Creation, Firm Evolution and Clusters in Chile’s Dynamic Wine Sector: Evidence from the Colchagua and Casablanca Regions
15. Trade and Empire, 1700-1870
16. The name is absent
17. Sustainability of economic development and governance patterns in water management - an overview on the reorganisation of public utilities in Campania, Italy, under EU Framework Directive in the field of water policy (2000/60/CE)
18. Human Rights Violations by the Executive: Complicity of the Judiciary in Cameroon?
19. Palvelujen vienti ja kansainvälistyminen
20. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.