A Recursive Method for Solving Assignment Problems.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
The recursive algorithm is a polynomially bounded nonsimplex method for solving assignment problems. It begins by finding the optimum solution for a problem defined from the first row, then finding the optimum for a problem defined from rows one and two, etc., continuing until it solves the problem consisting of all the rows. It is thus a dimension expanding rather than an improvement method such as as the simplex. During the method the row duals are non-increasing and the column duals non-decreasing. Best and worst case behavior is analyzed. It is shown that some problems can be solved in one pass through the data, while others may require many passes. The number of zero shifts comparable to degenerate pivots in the primal method is shown to be at most n-squared2. Extensive computational experience on the DEC-20 computer shows the method to be competitive for at least some kinds of assignment problems. Further tests on other computers are planned. Author
- Theoretical Mathematics