{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:19:44Z","timestamp":1765354784387,"version":"3.41.2"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["407714161"],"award-info":[{"award-number":["407714161"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>We present a new algorithm for solving the dense linear (sum) assignment problem and an efficient, parallel implementation that is based on the successive shortest path algorithm. More specifically, we introduce the well-known epsilon scaling approach used in the Auction algorithm to approximate the dual variables of the successive shortest path algorithm prior to solving the assignment problem to limit the complexity of the path search. This improves the runtime by several orders of magnitude for hard-to-solve real-world problems, making the runtime virtually independent of how hard the assignment is to find. In addition, our approach allows for using accelerators and\/or external compute resources to calculate individual rows of the cost matrix. This enables us to solve problems that are larger than what has been reported in the past, including the ability to efficiently solve problems whose cost matrix exceeds the available systems memory. To our knowledge, this is the first implementation that is able to solve problems with more than one trillion arcs in less than 100 hours on a single machine.<\/jats:p>","DOI":"10.1145\/3442348","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T19:08:06Z","timestamp":1618945686000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithm\u00a01015"],"prefix":"10.1145","volume":"47","author":[{"given":"Stefan","family":"Guthe","sequence":"first","affiliation":[{"name":"TU Darmstadt, Germany and Fraunhofer IGD, Germany"}]},{"given":"Daniel","family":"Thuerck","sequence":"additional","affiliation":[{"name":"NEC Laboratories, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584319"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584237"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186476"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition.","author":"Bychkovsky Vladimir","year":"2011","unstructured":"Vladimir Bychkovsky, Sylvain Paris, Eric Chan, and Fr\u00e9do Durand. 2011. Learning photographic global tonal adjustment with a database of input\/output image pairs. In Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.05.012"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00172-9"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/355958.355963"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317661"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.63"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"volume-title":"A Successive Shortest Path Algorithm\u00a0for the Assignment Problem","author":"Engquist M.","key":"e_1_2_2_13_1","unstructured":"M. Engquist. 1980. A Successive Shortest Path Algorithm\u00a0for the Assignment Problem. Defense Technical Information Center. Retrieved from https:\/\/books.google.de\/books?id&equals;IAQPOAAACAAJ."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221011"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"David S. Johnson and Catherine C. McGeoch (Eds.). 1993. Network Flows and Matching: First DIMACS Implementation Challenge. American Mathematical Society Boston MA. Retrieved from http:\/\/dimacs.rutgers.edu\/archive\/Volumes\/Vol12.html","DOI":"10.1090\/dimacs\/012"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","unstructured":"R. Jonker and A. Volgenant. 1987. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38 4 (01 Dec. 1987) 325--340. DOI:https:\/\/doi.org\/10.1007\/BF02278710","DOI":"10.1007\/BF02278710"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.268884"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_2_21_1","unstructured":"J. B. Orlin and Y. Lee. 1993. QuickMatch--A Very Fast Algorithm\u00a0for the Assignment Problem. Alfred P. Sloan School of Management Massachusetts Institute of Technology. Retrieved from https:\/\/books.google.de\/books?id&equals;Ci-qGwAACAAJ."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2010.11.003"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.09.001"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18461-6_50"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-016-0653-9"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1967.21.343"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010206"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03641-5_4"},{"key":"e_1_2_2_31_1","first-page":"5","article-title":"A certain zero-sum two-person game equivalent to the optimal assignment problem","volume":"2","author":"Neumann John Von","year":"1953","unstructured":"John Von Neumann. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contrib. Theor. Games 2, 0 (1953), 5--12.","journal-title":"Contrib. Theor. Games"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587584"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T22:26:49Z","timestamp":1752532009000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442348"}},"subtitle":["A Fast Scalable Solver for the Dense Linear (Sum) Assignment Problem"],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442348"],"URL":"https:\/\/doi.org\/10.1145\/3442348","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2021,4,20]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}