{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T03:50:19Z","timestamp":1778557819201,"version":"3.51.4"},"reference-count":54,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0166-218x(99)00172-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T13:35:45Z","timestamp":1027604145000},"page":"17-48","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":78,"title":["Algorithms and codes for dense assignment problems: the state of the art"],"prefix":"10.1016","volume":"100","author":[{"given":"Mauro","family":"Dell'Amico","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Toth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(99)00172-9_BIB1","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1287\/opre.40.1.S5","article-title":"The scaling network simplex algorithm","volume":"Suppl. 1","author":"Ahuja","year":"1992","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0167-6377(88)90082-X","article-title":"A sequential dual simplex algorithm for the linear assignment problem","volume":"7","author":"Akg\u00fcl","year":"1988","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0167-6377(89)90012-6","article-title":"Erratum. A sequential dual simplex algorithm for the linear assignment problem","volume":"8","author":"Akg\u00fcl","year":"1989","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB4","doi-asserted-by":"crossref","unstructured":"M. Akg\u00fcl, The linear assignment problem, in: M. Akg\u00fcl, H.W. Hamacher, S. T\u00fcfek\u00e7i (Eds.), Combinatorial Optimization NATO ASI Series F, vol. 82, Springer, Berlin, 1992, pp. 85\u2013122.","DOI":"10.1007\/978-3-642-77489-8_5"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0166-218X(93)90054-R","article-title":"A genuinely polynomial primal simplex algorithm for the assignment problem","volume":"45","author":"Akg\u00fcl","year":"1993","journal-title":"Discr. Appl. Math."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB6","unstructured":"P. Augerat, J.M. Belenguer, E. Benavent, A. Corber\u00e1n, D. Naddef, G. Rinaldi, Computational results with a branch and cut code for the capacitated vehicle routing problem, Tech. Rep. RR949-M, IMAG, Grenoble, France, 1995."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB7","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1145\/115234.115349","article-title":"A parallel augmenting shortest path algorithm for the assignment problem","volume":"38","author":"Balas","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB8","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1287\/moor.9.4.629","article-title":"The Hirsch conjecture for dual transportation polyhedra","volume":"9","author":"Balinski","year":"1984","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB9","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/opre.33.3.527","article-title":"Signature methods for the assignment problem","volume":"33","author":"Balinski","year":"1985","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01580579","article-title":"A competitive (dual) simplex method for the assignment problem","volume":"34","author":"Balinski","year":"1986","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01584319","article-title":"The alternating basis algorithm for assignment problems","volume":"13","author":"Barr","year":"1977","journal-title":"Math. Program"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB12","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1057\/jors.1990.21","article-title":"Linear programming on Cray supercomputers","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB13","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"Or-library: distributing test problems by electronic mail","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB14","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/BF01584237","article-title":"A new algorithm for the assignment problem","volume":"21","author":"Bertsekas","year":"1981","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB15","unstructured":"D.P. Bertsekas, Linear Network Optimization: Algorithms and Codes, The MIT Press, Cambridge, MA, 1991."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB16","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01589405","article-title":"Dual coordinate step methods for linear network flow problems","volume":"42","author":"Bertsekas","year":"1988","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB17","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/S0167-8191(05)80062-6","article-title":"Parallel synchronous and asynchronous implementations of the auction algorithm","volume":"17","author":"Bertsekas","year":"1991","journal-title":"Parallel Comput."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB18","doi-asserted-by":"crossref","unstructured":"R.E. Burkard, U. Derigs, Assignment and Matching Problems: Solution Methods with FORTRAN Programs, Springer, Berlin, 1980. R.E. Burkard, E. Cela, Linear assignment and extensions, Tech. Rep. 127, Institut f\u00fcr Mathematik, Technische Universit\u00e4t Graz (1998).","DOI":"10.1007\/978-3-642-51576-7"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB19","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/212066.212081","article-title":"Exact solution of large-scale, asymmetric traveling salesman problems","volume":"21","author":"Carpaneto","year":"1995","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB20","doi-asserted-by":"crossref","unstructured":"G. Carpaneto, S. Martello, P. Toth, Algorithms and codes for the assignment problem, in: B. Simeone, P. Toth, G. Gallo, F. Maffioli, S. Pallottino (Eds.), Fortran Codes for Network Optimization, Ann. Oper. Res., Vol. 13, Baltzer, Basel, 1988, pp. 193\u2013223.","DOI":"10.1007\/BF02288323"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB21","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/355873.355883","article-title":"Solution of the assignment problem","volume":"6","author":"Carpaneto","year":"1980","journal-title":"ACM, Trans. Math. Software"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB22","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0166-218X(87)90016-3","article-title":"Primal-dual algorithms for the assignment problem","volume":"18","author":"Carpaneto","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB23","doi-asserted-by":"crossref","unstructured":"D.A. Casta\u00f1on, Reverse auction algorithms for assignment problems, in: D.S. Johnson, C.C. McGeoch (Eds.), Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, Providence, RI, 1993, pp. 407\u2013430.","DOI":"10.1090\/dimacs\/012\/16"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1057\/jors.1969.75","article-title":"An Algorithm for the vehicle dispatching problem","volume":"20","author":"Christofides","year":"1969","journal-title":"Oper. Res. Quart."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB25","unstructured":"N. Christofides, A. Mingozzi, P. Toth, The vehicle routing problem, in: N. Christofides, A. Mingozzi, P. Toth, C. Sandi (Eds.), Combinatorial Optimization, Wiley, Chichester, 1979, pp. 318\u2013338."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF01580379","article-title":"A network simplex method","volume":"11","author":"Cunningham","year":"1976","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB27","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1287\/mnsc.39.1.115","article-title":"Heuristic algorithms for the multiple depot vehicle scheduling problem","volume":"39","author":"Dell'Amico","year":"1993","journal-title":"Manage. Sci."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB28","unstructured":"M. Dell'Amico, S. Martello, Linear assignment, in: M. Dell'Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, Chichester, 1997, pp. 355\u2013371."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB29","doi-asserted-by":"crossref","unstructured":"U. Derigs, The shortest augmenting path method for solving assignment problems \u2013 motivation and computational experience, in: C.L. Monma, (Ed.), Algorithms and Software for Optimization \u2013 Part I, Ann. Oper. Res., Vol. 4, Baltzer, Basel, 1985, pp. 57\u2013102.","DOI":"10.1007\/BF02022037"},{"issue":"4","key":"10.1016\/S0166-218X(99)00172-9_BIB30","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","article-title":"Optimal solution of vehicle routing problem using minimum k-trees","volume":"42","author":"Fisher","year":"1994","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB31","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585996","article-title":"An efficient cost scaling algorithm for the assignment problem","volume":"71","author":"Goldberg","year":"1995","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB32","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jagm.1993.1009","article-title":"Sublinear-time parallel algorithms for matching and related problemst","volume":"14","author":"Goldberg","year":"1993","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB33","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","article-title":"Finding minimum-cost circulation by successive approximation","volume":"15","author":"Goldberg","year":"1990","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB34","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1287\/opre.31.3.595","article-title":"A polynomial simplex method for the assignment problem","volume":"31","author":"Hung","year":"1983","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB35","doi-asserted-by":"crossref","unstructured":"D.S. Johnson, C.C. McGeoch (Eds.), Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, Providence, RI, 1993.","DOI":"10.1090\/dimacs\/012"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB36","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0167-6377(86)90073-8","article-title":"Improving the Hungarian assignment algorithm","volume":"5","author":"Jonker","year":"1986","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB37","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02278710","article-title":"A shortest augmenting path algorithm for dense and sparse linear assignment problems","volume":"38","author":"Jonker","year":"1987","journal-title":"Computing"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB38","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1287\/ijoc.3.4.299","article-title":"An empirical analysis of the dense assignment problem: Sequential and parallel implementations","volume":"3","author":"Kennington","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB39","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Naval Res. Logistics Quart."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB40","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/nav.3800030404","article-title":"Variants of The Hungarian method for the assignment problem","volume":"3","author":"Kuhn","year":"1956","journal-title":"Naval Res. Logistics Quart."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB41","unstructured":"E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB42","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/opre.24.1.190","article-title":"A hard assignment problem","volume":"24","author":"Machol","year":"1976","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB43","first-page":"364","article-title":"Errata","volume":"24","author":"Machol","year":"1977","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB44","doi-asserted-by":"crossref","unstructured":"S. Martello, P. Toth, Linear assignment problems, in: S. Martello, G. Laporte, M. Minoux, C. Ribeiro, (Eds.), Surveys in Combinatorial Optimization, Annals of Discrete. Mathematics, Vol. 31, North-Holland, Amsterdam, 1987, pp. 259\u2013282.","DOI":"10.1016\/S0304-0208(08)73238-9"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB45","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1287\/opre.31.2.277","article-title":"Implementation and testing of a primal-dual algorithm for the assignment problem","volume":"31","author":"McGinnis","year":"1983","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB46","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/BFb0121050","article-title":"On the simplex algorithm for networks and generalized networks","volume":"24","author":"Orlin","year":"1985","journal-title":"Math. Program. Stud."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB47","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01586040","article-title":"New scaling algorithms for the assignment and minimum cycle mean problems","volume":"54","author":"Orlin","year":"1992","journal-title":"Math. Program."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB48","unstructured":"C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB49","doi-asserted-by":"crossref","unstructured":"K.G. Ramakrishnan, N.K. Karmarkar, A.P. Kamath, An approximate dual projective algorithm for solving assignment problems, in: D.S. Johnson, C.C. McGeoch (Eds.), Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, Providence, RI, 1993, pp. 431\u2013452.","DOI":"10.1090\/dimacs\/012\/17"},{"key":"10.1016\/S0166-218X(99)00172-9_BIB50","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"Tsplib \u2013 A travelling salesman problem library","volume":"4","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB51","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0377-2217(94)90214-3","article-title":"A computational analysis of the auction algorithm","volume":"42","author":"Schwartz","year":"1994","journal-title":"European. J. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB52","unstructured":"B. Simeone, P. Toth, G. Gallo, F. Maffioli, S. Pallottino (Eds.), Fortran Codes for Network Optimization, Annals of Operation Research, Vol. 13, Baltzer, Basel, 1988."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB53","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1016\/0305-0548(96)00010-X","article-title":"Linear and semi-assignment problems: a core oriented approach","volume":"23","author":"Volgenant","year":"1996","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/S0166-218X(99)00172-9_BIB54","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01299157","article-title":"A comparison of two algorithms for the assignment problem","volume":"41","author":"Zaki","year":"1995","journal-title":"Comput. Opt. Appl."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X99001729?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X99001729?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T11:57:26Z","timestamp":1759060646000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X99001729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":54,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0166218X99001729"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(99)00172-9","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Algorithms and codes for dense assignment problems: the state of the art","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0166-218X(99)00172-9","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2000 Elsevier Science B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}