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

Paparrizos, Konstantinos

RAIRO, Rech. Opér. 22, No. 3, 269-289 (1988).

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

MSC:

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

Keywords:

signature methods; dual relaxation procedure; assignment; consecutive stages

Citations:

Zbl 0527.90069