{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T06:51:30Z","timestamp":1778568690200,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,2,7]],"date-time":"2015-02-07T00:00:00Z","timestamp":1423267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1144466, 1141022, 1217231, 1406304, 1438963"],"award-info":[{"award-number":["1144466, 1141022, 1217231, 1406304, 1438963"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,2,7]]},"DOI":"10.1145\/2716282.2716287","type":"proceedings-article","created":{"date-parts":[[2015,2,3]],"date-time":"2015-02-03T13:43:17Z","timestamp":1422970997000},"page":"99-108","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Rethinking the parallelization of random-restart hill climbing: a case study in optimizing a 2-opt TSP solver for GPU execution"],"prefix":"10.1145","author":[{"given":"Molly A.","family":"O'Neil","sequence":"first","affiliation":[{"name":"Texas State University, USA"}]},{"given":"Martin","family":"Burtscher","sequence":"additional","affiliation":[{"name":"Texas State University, USA"}]}],"member":"320","published-online":{"date-parts":[[2015,2,7]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.10.3.350"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICICIC.2009.255"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.01.002"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Chen S. Davis S. Jiang H. and Novobilski A. 2011. CUDABased Genetic Algorithm on Traveling Salesman Problem. Computer and Information Science 2011 R. Lee Ed. Springer Berlin Heidelberg 241-252.  Chen S. Davis S. Jiang H. and Novobilski A. 2011. CUDABased Genetic Algorithm on Traveling Salesman Problem. Computer and Information Science 2011 R. Lee Ed. Springer Berlin Heidelberg 241-252.","DOI":"10.1007\/978-3-642-21378-6_19"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2961491.2961523"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.01.003"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585892"},{"key":"e_1_3_2_1_11_1","first-page":"4","article-title":"The Travelling Salesman Problem and its Application in Logistic Practice","volume":"8","author":"Exnar F.","year":"2011","unstructured":"Exnar , F. , Macha\u010d , O. 2011 . The Travelling Salesman Problem and its Application in Logistic Practice . WSEAS Transactions on Business and Economics 8 , 4 (Oct. 2011), 163\u2013173. Exnar, F., Macha\u010d, O. 2011. The Travelling Salesman Problem and its Application in Logistic Practice. WSEAS Transactions on Business and Economics 8, 4 (Oct. 2011), 163\u2013173.","journal-title":"WSEAS Transactions on Business and Economics"},{"key":"e_1_3_2_1_12_1","volume-title":"Department of Genetics","author":"Felsenstein J.","unstructured":"Felsenstein , J. 1995. PHYLIP ( Phylogeny Inference Package ). Distributed by the author , Department of Genetics , University of Washington , http:\/\/evolution.genetics.washington.edu\/phylip.html. Felsenstein, J. 1995. PHYLIP (Phylogeny Inference Package). Distributed by the author, Department of Genetics, University of Washington, http:\/\/evolution.genetics.washington.edu\/phylip.html."},{"key":"e_1_3_2_1_13_1","first-page":"264","volume-title":"Proceedings of the Seventh International Conference on Numerical Methods and Applications (Aug.","author":"Fujimoto N.","year":"2010","unstructured":"Fujimoto , N. and Tsutsui , S . 2010. A Highly-Parallel TSP Solver for a GPU Computing Platform . Proceedings of the Seventh International Conference on Numerical Methods and Applications (Aug. 2010 ), 264 - 271 . Fujimoto, N. and Tsutsui, S. 2010. A Highly-Parallel TSP Solver for a GPU Computing Platform. Proceedings of the Seventh International Conference on Numerical Methods and Applications (Aug. 2010), 264-271."},{"key":"e_1_3_2_1_14_1","unstructured":"Garey M.R. and Johnson D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.   Garey M.R. and Johnson D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman."},{"key":"e_1_3_2_1_15_1","volume-title":"The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization","author":"Johnson D.","unstructured":"Johnson , D. and McGeoch , L. 1997. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization , E. Aarts and J. Lenstra, Eds. John Wiley and Sons , 215-310. 0 0.5 1 1.5 2 2.5 3 Spe edu p \u00a0 of \u00a0 tu ned ov er \u00a0ca lc cod e \u00a0 (cl im be rs\/se c) Number \u00a0of \u00a0cities Figure 8. Speedup in climbers\/second throughput of tuned over calc, measured using the same climber count and initial tour Johnson, D. and McGeoch, L. 1997. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization, E. Aarts and J. Lenstra, Eds. John Wiley and Sons, 215-310. 0 0.5 1 1.5 2 2.5 3 Spe edu p \u00a0 of \u00a0 tu ned ov er \u00a0ca lc cod e \u00a0 (cl im be rs\/se c) Number \u00a0of \u00a0cities Figure 8. Speedup in climbers\/second throughput of tuned over calc, measured using the same climber count and initial tour"},{"key":"e_1_3_2_1_16_1","first-page":"4","article-title":"Some Simple Applications of the Travelling Salesman Problem","volume":"26","author":"Lenstra J.K.","year":"1975","unstructured":"Lenstra , J.K. and Rinnooy Kan , A.H.G. 1975 . Some Simple Applications of the Travelling Salesman Problem . Oper. Res. 26 , 4 (Nov. 1975), 717-733. Lenstra, J.K. and Rinnooy Kan, A.H.G. 1975. Some Simple Applications of the Travelling Salesman Problem. Oper. Res. 26, 4 (Nov. 1975), 717-733.","journal-title":"Oper. Res."},{"key":"e_1_3_2_1_17_1","volume-title":"Multi-Start Methods. Handbook of Metaheuristics","author":"Marti R.","unstructured":"Marti , R. 2003. Multi-Start Methods. Handbook of Metaheuristics , F. Glover and G.A. Kochenberger, Eds. Springer US , 355-368. Marti, R. 2003. Multi-Start Methods. Handbook of Metaheuristics, F. Glover and G.A. Kochenberger, Eds. Springer US, 355-368."},{"key":"e_1_3_2_1_18_1","first-page":"11","article-title":"Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums 2. Teubner","author":"Menger K.","year":"1932","unstructured":"Menger , K. 1932 . Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums 2. Teubner , Leipzig , 11 - 23 . Menger, K. 1932. Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums 2. Teubner, Leipzig, 11-23.","journal-title":"Leipzig"},{"key":"e_1_3_2_1_19_1","first-page":"348","volume-title":"Proceedings of the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (Jul.","author":"O\u2019Neil M.A.","year":"2011","unstructured":"O\u2019Neil , M.A. , Tamir , D. , and Burtscher , M . 2011. A Parallel GPU Version of the Traveling Salesman Problem . Proceedings of the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (Jul. 2011 ), 348 - 353 . O\u2019Neil, M.A., Tamir, D., and Burtscher, M. 2011. A Parallel GPU Version of the Traveling Salesman Problem. Proceedings of the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (Jul. 2011), 348-353."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2009.43"},{"key":"e_1_3_2_1_22_1","first-page":"309","article-title":"Local Search and Metaheuristics. Traveling Salesman Problem and its Variations, G. Gutin and A.P. Punnen, Eds. Kluwer Academic Publishers","author":"Rego C.","year":"2002","unstructured":"Rego , C. and Glover , F. 2002 . Local Search and Metaheuristics. Traveling Salesman Problem and its Variations, G. Gutin and A.P. Punnen, Eds. Kluwer Academic Publishers , Dordrecht , 309 - 368 . Rego, C. and Glover, F. 2002. Local Search and Metaheuristics. Traveling Salesman Problem and its Variations, G. Gutin and A.P. Punnen, Eds. Kluwer Academic Publishers, Dordrecht, 309-368.","journal-title":"Dordrecht"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCSim.2012.6266963"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330784.2330978"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.227"},{"key":"e_1_3_2_1_26_1","unstructured":"TSPLIB http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/.  TSPLIB http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNC.2012.22"}],"event":{"name":"GPGPU-8: General-purpose Processing with Graphics Processing Units 8","location":"San Francisco CA USA","acronym":"GPGPU-8","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 8th Workshop on General Purpose Processing using GPUs"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716282.2716287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2716282.2716287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:42Z","timestamp":1750230042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716282.2716287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,7]]},"references-count":26,"alternative-id":["10.1145\/2716282.2716287","10.1145\/2716282"],"URL":"https:\/\/doi.org\/10.1145\/2716282.2716287","relation":{},"subject":[],"published":{"date-parts":[[2015,2,7]]},"assertion":[{"value":"2015-02-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}