## A sequential dual simplex algorithm for the linear assignment problem.(English)Zbl 0654.90053

The linear assignment problem is viewed as an instance of the transshipment problem over a directed bipartite graph G. First the corresponding dual simplex method and its relationship to graphs is described in detail. This method starts with a dual feasible tree (paragraph 1). As a preliminary the already known “strongly feasible trees” and the “dual strongly feasible trees” for the assignment problem are introduced, certain properties are derived and the dual simplex algorithm of Balinski, which works in stages is described.
The main result consists of a new algorithm (paragraph 2) which also works with dual strongly feasible trees; but here a sequence of assignment problems over an increasing sequence of graphs each of which defines such a problem is solved. This algorithm gives the possibility to handle rectangular systems (i.e. for the set of vertices $$N=U\cup V$$ of G the sizes of U and V are different) in a natural manner, i.e. without any transformations which, for example, needs the Hungarian algorithm.
Finally (paragraph 3) it is shown that the developed algorithm works with $$O(n^ 2)$$ pivots and $$O(n^ 2\log n+nm)$$ time complexity, i.e. the same complexity as other algorithms known in the literature.
Reviewer: H.-J.Presia

### MSC:

 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C35 Programming involving graphs or networks 68Q25 Analysis of algorithms and problem complexity
Full Text:

### References:

  Akgül, M., A genuinenly polynomial primal simplex algorithm for the assignment problems, (SERC Report IEOR 87-07 (1987), Bilkent University)  Akgül, M., Variations on a theme of Balinski: Signature methods for the linear assignment problem, (SERC Report IEOR-8802 (1988), Bilkent University)  Balinski, M., (Presented at Mathematical Programming Symposium. Presented at Mathematical Programming Symposium, Bonn (1982)) · Zbl 0583.90064  Balinski, M., A competitive (dual) simplex method for the assignment problem, Mathematical Programming, 34, 125-141 (1986) · Zbl 0596.90064  Barr, R.; Glover, F.; Klingman, D., The alternating basis algorithm for assignment problem, Mathematical Programming, 13, 1-3 (1977) · Zbl 0378.90097  Cunningham, W., A network simplex method, Mathematical Programming, 11, 105-116 (1976) · Zbl 0352.90039  Fredman, M.; Tarjan, R., (Proc. 25-th FOCS (1984)), 339-346, Also in · Zbl 1412.68048  Goldfarb, D., Efficient dual simplex algorithms for the assignment problem, Mathematical Programming, 37, 187-203 (1985) · Zbl 0578.90051  Tarjan, R., Data Structures and Network Algorithms (1983), SIAM: SIAM Philadelphia, PA · Zbl 0584.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.