{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T05:40:15Z","timestamp":1698126015184},"reference-count":20,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,24]],"date-time":"2006-10-24T00:00:00Z","timestamp":1161648000000},"content-version":"vor","delay-in-days":5319,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1992,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper discusses efforts to develop parallel algorithms that can be used to solve large\u2010scale assignment problems typical of military battle management systems. Attempts to parallellze the classical Hungarian method are explored. Drawing on experimental data, a regresslon model is derived that relates the Hungarian method's run time to a cubic function of the number of parallel processors used in the solution. Four parallel heuristics for solving the assignment problem are developed and analysed. Two of them perform well in a parallel environment. The first, based on Vagel's approximation, can be used to identify a feasible, near\u2010optimal assignment. The second algorithm partitions the assignment problem into independent subproblems across the parallel array. The resulting solution, although infeasible in the strict definition of the assignment problem, is seen to be reasonably good and can be obtained very rapidly. Either of these two heuristics are of potential use in the stringent computing environment of a real\u2010time resource management system.<\/jats:p>","DOI":"10.1002\/cpe.4330040205","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T09:08:18Z","timestamp":1163840898000},"page":"163-184","source":"Crossref","is-referenced-by-count":0,"title":["Parallel approaches to the solution of the assignment problem"],"prefix":"10.1002","volume":"4","author":[{"suffix":"IV","given":"Nathaniel J.","family":"Davis","sequence":"first","affiliation":[]},{"given":"Barry A.","family":"Carpenter","sequence":"additional","affiliation":[]},{"given":"Charles W.","family":"Glover","sequence":"additional","affiliation":[]},{"given":"Jean\u2010Christophe","family":"Culioli","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,24]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Introduction to Operations Research","author":"Churchman C. W.","year":"1957"},{"key":"e_1_2_1_3_2","volume-title":"Linear Programming","author":"Kreko B.","year":"1968"},{"key":"e_1_2_1_4_2","volume-title":"Linear Programming in Single and Multiple\u2010Objective Systems","author":"Ignizio J. P.","year":"1982"},{"key":"e_1_2_1_5_2","unstructured":"B. A.Carpenter Implementation and Performance Analysis of Parallel Assignment Algorithm on a Hypercube Computer Master's Thesis Department of Electrical and Computer Engineering Air Force Institute of Technology Wright\u2010Patterson Air Force Base OH 1987."},{"key":"e_1_2_1_6_2","unstructured":"J. C.CulioliandV.Protopopescu \u2018A new algorithm for linear\u2010programming that is easy to implement: application to transportation problem\u2019 Oak Ridge National Laboratory TM\u201010929 Oak Ridge Tennessee August1988."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/355873.355883"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584237"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/362919.362945"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/362919.362948"},{"issue":"9","key":"e_1_2_1_13_2","first-page":"36","article-title":"SDI: The grand experiment. Mind boggling complexity","volume":"22","author":"Adams J. A.","year":"1985","journal-title":"IEEE Spectrum"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"S. C.Chang R. M.JamesandJ. J.Shaw \u2018Assignment algorithms for kinetic energy weapons in boost phase defense\u2019 26th Conference on Decision and Control December1987.","DOI":"10.1109\/CDC.1987.272755"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676924"},{"key":"e_1_2_1_16_2","volume-title":"High\u2010Performance Computer Architecture","author":"Stone H. S.","year":"1987"},{"key":"e_1_2_1_17_2","first-page":"408","article-title":"Speedup versus efficiency in parallel systems","volume":"38","author":"Eager D. L.","year":"1989","journal-title":"IEEE Trans."},{"key":"e_1_2_1_18_2","first-page":"257","article-title":"Predicting performance of parallel computations","volume":"1","author":"Mak V. W.","year":"1990","journal-title":"IEEE Trans."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1177\/003754979105600308"},{"key":"e_1_2_1_20_2","unstructured":"J. C.Culioli C. W.Glover J. P.JonesandC.Roe \u2018NCUBE implementation of some heuristics and an optimal algorithm for large\u2010scale assignment problems\u2019 Fourth Conference on Hypercubes Concurrent Computers and Applications March1989 pp.391\u2013394."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90025-2"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330040205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330040205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T00:33:02Z","timestamp":1698107582000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330040205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,4]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,4]]}},"alternative-id":["10.1002\/cpe.4330040205"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330040205","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,4]]}}}