## Signature methods for the assignment problem.(English)Zbl 0583.90064

Given an $$n\times n$$-matrix $$C=(c_{ij})$$ the assignment problem is to find a permutation p of the indices $$1,\ldots,n$$ that minimizes $$\sum_{i}c_{ip(i)}$$. Let the set of n nodes R resp. C represent the set of row resp. column indices. Moreover, let T be any spanning tree of edges (i,j), $$i\in R$$, $$j\in C$$ together with two vectors u, v such that $$u_ i+v_ j=c_{ij}$$ for (i,j)$$\in T$$, $$u_ i+v_ j\leq c_{ij}$$ for (i,j)$$\not\in T$$. The signature of such a tree T(u,v) is the vector of its row node degrees. The method proposed in this paper seeks a tree whose signature contains exactly one 1 and otherwise 2’s, a tree which is shown to produce a solution of the problem in a straightforward way. It iterates from one tree T to another ”neighboring” tree T’ obtained by a special operation of pivoting on an edge (k,l) of T. First, a method entirely guided by signatures is presented, which terminates in at most (n-1)(n-2)/2 steps. Then it is shown how primal information can be adjoined. Finally, the worst-case bound given is proven also to be best possible.
Reviewer: R.Euler

### MSC:

 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 05C05 Trees 65K05 Numerical mathematical programming methods
Full Text: