Abstract
We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.
Zusammenfassung
Wir entwickeln einen Algorithmus mit kürzesten alternierenden Wegen für das lineare Zuordnungsproblem. Er enthält neue Routinen für die Anfangswerte und eine spezielle Implementierung der Kürzesten-Wege-Methode von Dijkstra. Sowohl für dichte als auch für dünne Probleme zeigen Testläufe, daß unser Algorithmus gleichmäßig schneller als die besten Algorithmen aus der Literatur ist. Eine Implementierung in Pascal wird angegeben.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Balinski, M. L.: Signature methods for the assignment problem. Operations Research33, 527–536 (1985).
Barr, R., Glover, F., Klingman, D.: The alternating path basis algorithm for assignment problems. Mathematical Programming13, 1–13 (1977).
Bertsekas, D. P.: A new algorithm for the linear assignment problem. Mathematical Programming21, 152–171 (1981).
Burkard, R. E., Derigs, U.: Assignment and Matching Problems: Solution Methods with Fortran Programs, pp. 1–11. Berlin-Heidelberg-New York: Springer 1980.
Carpaneto, G., Toth, P.: Algorithm 548 (solution of the assignment problem). ACM Transactions on Mathematical Software6, 104–111 (1980).
Carpaneto, G., Toth, P.: Algorithm 50: algorithm for the solution of the assignment problem for sparse matrices. Computing31, 83–94 (1983).
Carraresi, P., Sodini, C.: An efficient algorithm for the bipartite matching problem. European Journal of Operational Research23, 86–93 (1986).
Derigs, U., Metz, A.: An efficient labeling technique for solving sparse assignment problems. Computing36, 301–311 (1986).
Derigs, U., Metz, A.: An in-core/out-of-core method for solving large scale assignment problems. Zeitschrift für Operations Research30, 181–195 (1986).
Dorhout, B.: Het Lineaire Toewijzingsprobleem: Vergelijking van Algorithmen. Rapport BN 21/73, Mathematisch Centrum, Amsterdam (1973).
Dorhout, B.: Experiments with some algorithms for the linear assignment problem. Report BW 39, Mathematisch Centrum, Amsterdam (1975).
Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik1, 269–271 (1959).
Edmonds, J., Karp, R. M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM19, 248–264 (1972).
Ford jr., L. R., Fulkerson, D. R.: Flows in Networks. Princeton: Princeton University Press 1962.
Glover, F., Klingman, D., Phillips, N.: A new polynomially bounded shortest path algorithm. Operations Research33, 65–73 (1985).
Glover, F., Klingman, D., Phillips, N., Schneider, R.: New polynomial shortest path algorithms and their computational attributes. Management Science31, 1106–1128 (1985).
Goldfarb, D.: Efficient dual simplex algorithms for the assignment problem. Mathematical Programming33, 187–203 (1985).
Hung, M. S., Rom, W. O.: Solving the assignment problem by relaxation. Operations Research28, 969–982 (1980).
Jonker, R.: Traveling salesman and assignment algorithms: design and implementation. Faculty of Actuarial Science and Econometrics, University of Amsterdam (1986).
Jonker, R., Volgenant, A.: Improving the Hungarian assignment algorithm. Operations Research Letters5, 171–175 (1986).
Karp, R. M.: An algorithm to solve them×n assignment problem in expected timeO (mn logn). Networks10, 143–152 (1980).
Kuhn, H. W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly2, 83–97 (1955).
Lawler, E. L.: Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart & Winston 1976.
Mack, C.: The Bradford method for the assignment problem. New Journal of Statistics and Operational Research1, 17–29 (1969).
McGinnis, L. F.: Implementation and testing of a primal-dual algorithm for the assignment problem. Operations Research31, 277–291 (1983).
Papadimitriou, C. H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, N. J.: Prentice-Hall 1982.
Silver, R.: An algorithm for the assignment problem. Communications of the ACM3, 605–606 (1960).
Tabourier, Y.: Un Algorithme pour le Problème d'Affectation. R.A.I.R.O. Recherche Opérationnelle/Operations Research6, 3–15 (1972).
Tomizawa, N.: On some techniques useful for the solution of transportation problems. Networks1, 173–194 (1971).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jonker, R., Volgenant, A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987). https://doi.org/10.1007/BF02278710
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02278710