A relaxation column signature method for assignment problems

DOI10.1016/0377-2217(91)90243-OMaRDI QIDQ1814258zbMATH OpenFDO

Authors Konstantinos Paparrizos

Publication date 25 June 1992

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(91)90243-O

zbMATH Keywords

assignment problemscolumn signature methodsimplex method

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Discrete location and assignment (90B80) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The author presents a column signature method for solving assignment problems. It is shown that by this method an \(n\times n\) assignment problem can be solved in at most \({1 \over 2}(n-1)(n-2)\) iterations and in at most \(O(n^ 3)\) elementary operations. It is also shown that the average number of iterations required by the method to arrive at a solution is bounded from above by \(n \log n\). Some similarities between the presented method and other known methods including the modified Hung- Rom algorithm [\textit{M. S. Hung} and \textit{W. O. Rom}, Oper. Res. 28, 969- 982 (1980; Zbl 0441.90062)] are discussed at the end.

Recommendations

• Signature Methods for the Assignment Problem
• A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
• Efficient dual simplex algorithms for the assignment problem
• On solving a variation of the assignment problem

Cites work

• A competitive (dual) simplex method for the assignment problem
• A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
• Efficient dual simplex algorithms for the assignment problem
• Faces of dual transportation polyhedra
• Signature Methods for the Assignment Problem
• Solving the Assignment Problem by Relaxation
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems

Cited in

(5)

• On solving a variation of the assignment problem
• Signature Methods for the Assignment Problem
• Exterior point simplex-type algorithms for linear and network optimization problems
• On the initialization methods of an exterior point algorithm for the assignment problem
• Signature classes of transportation polytopes

This page was built for publication: A relaxation column signature method for assignment problems

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