The partial orthogonalization process and its application to the optimal assignment problem

MaRDI QIDQ2706804zbMATH OpenFDO

Authors D. S. Dadayan, A. D. Tuniev

Publication date 27 March 2001

Published in Uchenye Zapiski. Artsakhskiĭ Gosudarstvennyĭ Universitet (Search for Journal in Brave)

zbMATH Keywords

assignment problemlinear programmingorthogonalization process

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)

Review text

Using a partial orthogonalization process it is proved that the vector \([1/n,1/n, \dots, 1/n]\) is a feasible normal solution of the well known assignment problem: find \(\min CX\) under the constraints \(AX=1\), \(X\geq 0\), where \((2n,n^2)\) matrix \(A\) has corresponding structure with \(0,1\) elements. An explicit form of the simplex table for this solution is derived which can be used as an initial table for subsequent iterations.NEWLINENEWLINENEWLINEUnfortunately, the paper under review contains errors, namely in somewhat confusing notation.

Recommendations

• A note on an orthogonal systolic design for the assignment problem
• A new method of solving assignment problems -- the target value submatrix method
• The recurrent method to solve the assignment problem
• A note on Hungarian algorithm for assignment problems
• Method of sequential modification of the objective function in the assignment problem

This page was built for publication: The partial orthogonalization process and its application to the optimal assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706804)