assigned to job j only if (i, j) is from a given set of feasible transitions. This can
obviously be represented by a {0, -∞} matrix C, where a 0 corresponds to a
feasible move. Alternatively, this version can be represented by a (non-weighted)
digraph D = (V, E), where V = {v1, v2, . . . , vn} and E = {(vi, vj); cij = 0}.
The number of principal submatrices of order k of a matrix of order n is
nk . Therefore if k is an input variable, solving the assignment problem for all
principal submatrices and then comparing the resulting values would be non-
polynomial. If k ≤ n is fixed, then the method would be polynomial (though
of a high degree in most cases). However, the total number of submatrices of
all orders is kn=1 nk = 2n - 1 and therefore checking all of them would not
solve JRP for all k in polynomial time. In fact, no polynomial method seems
to be known for solving this problem, neither is it proved to be N P -hard. In
this paper we present a number of cases when JRP is solvable polynomially.
Note that there is a randomized polynomial algorithm for solving JRP [5]. It
may be interesting to mention that the problem arising by removing the word
“principal” from the formulation of the JRP is easily solvable [10].
In Section 2 we will give an overview of known results. Section 3 deals
with matrices over T = {-∞, 0} and Section 4 contains results for matrices
over R := R U {-∞}. These include the proof that JRP(A) can be solved
in polynomial time if this is true for every irreducible diagonal block of the
Frobenius normal form of A.
2 Definitions and known results
In the rest of the paper we will assume that n ≥ 1 is a given integer and we
denote by N the set {1,..., n}. If A = (aij) ∈ Rn×n then we denote
m(A) = m∈aPx ai,π(i)
π∈ n i∈N
where Pn stands for the set of all permutations of the set N . The quantity
ai,π(i) will be called the weight of π (notation w(A, π)). Obviously, m(A) is
i∈N
the optimal value of the assignment problem for the matrix A. The set of all
optimal permutations will be denoted by ap(A), that is,
ap(A) = {π ∈ Pn; m(A) = ai,π(i)}.
i∈N