×

A dual forest algorithm for the assignment problem. (English) Zbl 0743.90077

Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 1-10 (1991).

Show indexed articles as search result.

Summary: [For the entire collection see Zbl 0726.00015.]
A new algorithm for the (linear) assignment problem is presented. The algorithm is of dual nature but dual feasibility is relaxed. The iterations are guided by valency structure of forests which represent the dual solutions. Some computational experience is presented.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Citations:

Zbl 0726.00015
PDFBibTeX XMLCite