A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem. (English) Zbl 0664.90055

The author first introduces a new dual relaxation procedure for solving the assignment problem consisting of consecutive stages. At the beginning of each of these stages the corresponding basic tree is dually feasible, whereas intermediate trees are in general not dually feasible. The per unit improvement of the objective function is in this algorithm non- decreasing.
Next the new algorithm is combined with signature ideas as introduced by M. L. Balinski [C. R. Acad. Sci., Paris, Ser. I 296, 457-459 (1983; Zbl 0527.90069)]. The resulting algorithm is shown to have a complexity of \(O(n^ 4)\). The idea can be carried over to transportation problems by introducing two different types of stages. Special techniques are developed for sparse problems.
Reviewer: H.Hamacher


90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity


Zbl 0527.90069
Full Text: DOI EuDML