{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:18:31Z","timestamp":1762273111359,"version":"3.40.5"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2047\/1 \u2013 390685813"],"award-info":[{"award-number":["EXC-2047\/1 \u2013 390685813"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,8,31]]},"DOI":"10.1137\/21m146199x","type":"journal-article","created":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T09:19:39Z","timestamp":1689844779000},"page":"841-864","source":"Crossref","is-referenced-by-count":10,"title":["The Approximation Ratio of the <i>k<\/i>-Opt Heuristic for the Euclidean Traveling Salesman Problem"],"prefix":"10.1137","volume":"52","author":[{"given":"Ulrich A.","family":"Brodowsky","sequence":"first","affiliation":[{"name":"52076 Aachen, Germany."}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8656-3418","authenticated-orcid":true,"given":"Stefan","family":"Hougardy","sequence":"additional","affiliation":[{"name":"Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics, University of Bonn, 53113 Bonn, Germany."}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3812-2903","authenticated-orcid":true,"given":"Xianghui","family":"Zhong","sequence":"additional","affiliation":[{"name":"Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics, University of Bonn, 53113 Bonn, Germany."}]}],"member":"351","published-online":{"date-parts":[[2023,7,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.387"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251244"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s43069-021-00101-z"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.4.1.61"},{"volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"ref7"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.05.007"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"volume-title":"The Traveling Salesman: Computational Solutions for TSP Applications","year":"1994","author":"Reinelt G.","key":"ref13"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"ref15","first-page":"76","volume":"17","author":"Serdyukov A. I.","year":"1978","journal-title":"Upravlyaemye sistemy"},{"volume-title":"Approximation Algorithms for the Traveling Salesman Problem","year":"2020","author":"Zhong X.","key":"ref17"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2021.05.012"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T18:15:56Z","timestamp":1693505756000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M146199X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,20]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1137\/21M146199X"],"URL":"https:\/\/doi.org\/10.1137\/21m146199x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"type":"print","value":"0097-5397"},{"type":"electronic","value":"1095-7111"}],"subject":[],"published":{"date-parts":[[2023,7,20]]}}}