NEW ALGORITHMS FOR ASSIGNMENT AND TRANSPORTATION PROBLEMS

A new method for solving the classical assignment problem is proposed. In some ways the algorithm resembles the Hungarian method. The worst case computational complexity of one implementation of the algorithm for full dense, all integer, NxN problems is the same as the Hungarian method. However, the average complexity of the algorithm seems to be considerably better than the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. On heuristic grounds, it appears that the new method owes its good performance principally to a phenomenon referred to as "outpricing", a property of the method whereby during the course of the algorithm the prices of some sinks are increased by large increments, much larger than in the Hungarian method. As a consequence, these sinks are temporarily or permanently outpriced by other sinks and are, in effect, driven out of the problem in the sense that they do no get labeled and scanned further for relatively long time periods. As a result, the algorithm requires fewer row operations since it deals with a problem of lower dimension.

  • Corporate Authors:

    Massachusetts Institute of Technology

    Laboratory for Information and Decision Systems
    Cambridge, MA  USA  01239

    National Science Foundation

    Engineeing and Applied Science, 1800 G Street, NW
    Washington, DC  USA  20550
  • Authors:
    • Bertsekas, D P
  • Publication Date: 1979-9

Media Info

  • Pagination: 46 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00326910
  • Record Type: Publication
  • Source Agency: National Technical Information Service
  • Report/Paper Numbers: LIDS-R-945, NSF/RA-790509
  • Contract Numbers: NSF-ENG79-06332
  • Files: TRIS
  • Created Date: Feb 18 1981 12:00AM