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


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: DOI


[1] Akgül, M., A genuinenly polynomial primal simplex algorithm for the assignment problems, (SERC Report IEOR 87-07 (1987), Bilkent University)
[2] Akgül, M., Variations on a theme of Balinski: Signature methods for the linear assignment problem, (SERC Report IEOR-8802 (1988), Bilkent University)
[3] Balinski, M., (Presented at Mathematical Programming Symposium. Presented at Mathematical Programming Symposium, Bonn (1982)) · Zbl 0583.90064
[4] Balinski, M., A competitive (dual) simplex method for the assignment problem, Mathematical Programming, 34, 125-141 (1986) · Zbl 0596.90064
[5] Barr, R.; Glover, F.; Klingman, D., The alternating basis algorithm for assignment problem, Mathematical Programming, 13, 1-3 (1977) · Zbl 0378.90097
[6] Cunningham, W., A network simplex method, Mathematical Programming, 11, 105-116 (1976) · Zbl 0352.90039
[7] Fredman, M.; Tarjan, R., (Proc. 25-th FOCS (1984)), 339-346, Also in · Zbl 1412.68048
[8] Goldfarb, D., Efficient dual simplex algorithms for the assignment problem, Mathematical Programming, 37, 187-203 (1985) · Zbl 0578.90051
[9] 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.