A sequential dual simplex algorithm for the linear assignment problem (Q1108928): Difference between revisions

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.