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

Balinski, M. L.

Oper. Res. 33, 527-536 (1985).

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

Keywords:

neighboring tree; signature of a tree; assignment; spanning tree; pivoting; worst-case bound