Abstract
We describe a new implementation of the shortest augmenting path approach for solving sparse assignment problems and report computational experience documenting its efficiency.
Zusammenfassung
Wir beschreiben eine neue Implementierung der kürzesten-erweiternden-Wege-Methode zur Lösung dünner Zuordnungsprobleme und berichten über numerische Untersuchungen, die die Effizienz dieser Implementierung dokumentieren.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balinski, M., Gomory, R.: A primal method for the assigment and transportation problem. Management Science10, 578–593 (1964).
Balinski, M.: The signature methods for the assignment problem. Operations Research33, 527–536 (1985).
Burkard, R., Derigs, U.: Assignment and matching problems. Solution methods with FORTRAN Programs. Springer Lecture Notes in Economics and Mathematical Systems No. 184 (1984).
Carpaneto, G., Toth, P.: Algorithm/Algorithmus 50 — Algorithm for solution of the assignment problem for sparse matrices. Computing31, 83–94 (1983).
Derigs, U.: The shortest augmenting path method for solving assignment problems — Motivation and computational experience. Report No. 84328. Institute of Operations Research, University of Bonn, 1984. To appear in Annals of Operations Research.
Dial, R.: Algorithm 360: Shortest path forest with topological ordering. Communications of the ACM12, 632–633 (1969).
Glover, F., Klingman, D.: A computer study of efficient algorithms for shortest path trees and assignment problems. Research Report CCS 430, Center for Cybernetic Studies, The University of Texas (1982).
Hung, M. S., Rom, W. D.: Solving the assignment problem by relaxation. Operations Research28, 969–982 (1980).
Karney, D., Klingman, D.: Netgen revisited: A program for generating large scale (un) capaciated assignment, transportation, and minimum cost network problems. Research Report CCS 320, Center for Cybernetic Studies. The University of Texas (1978).
Kuhn, H. W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly2, 83–97 (1955).
Thompson, G. L.: A recursive method for solving assignment problems. In: Studies on Graphs and Discrete Programming (Hansen, P., ed.). Annals of Discrete Mathematics11, 319–343 (1981).
Author information
Authors and Affiliations
Additional information
Dedicated to Professor W. Knödel on the occasion of his 60th birthday
Supported by Sonderforschungsbereich 21 (DFG), Institut für Operations Research, Universität Bonn, Federal Republic of Germany.
Rights and permissions
About this article
Cite this article
Derigs, U., Metz, A. An efficient labeling technique for solving sparse assignment problems. Computing 36, 301–311 (1986). https://doi.org/10.1007/BF02240205
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02240205