A Recursive Method for Solving Assignment Problems.
Abstract
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-squared/2. 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1979
- Accession Number
- ADA083596
Entities
People
- Gerald L. Thompson
Organizations
- Carnegie Mellon University