{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:49:08Z","timestamp":1776358148124,"version":"3.51.2"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003182","name":"Siberian Branch, Russian Academy of Sciences","doi-asserted-by":"publisher","award":["0314-2019-0014"],"award-info":[{"award-number":["0314-2019-0014"]}],"id":[{"id":"10.13039\/501100003182","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s11590-021-01769-2","type":"journal-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T09:02:57Z","timestamp":1623834177000},"page":"2115-2122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-1994","authenticated-orcid":false,"given":"Vladimir","family":"Shenmaier","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"issue":"5","key":"1769_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"1769_CR2","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1137\/130913328","volume":"45","author":"Y Bartal","year":"2016","unstructured":"Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput. 45(4), 1563\u20131581 (2016)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1769_CR3","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1145\/876638.876640","volume":"50","author":"A Barvinok","year":"2003","unstructured":"Barvinok, A., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641\u2013664 (2003)","journal-title":"J. ACM"},{"key":"1769_CR4","first-page":"585","volume-title":"The traveling salesman problem and its applications","author":"AI Barvinok","year":"2002","unstructured":"Barvinok, A.I., Gimadi, E.K., Serdyukov, A.I.: The maximum traveling salesman problem. In: Gutin, G., Punnen, A.P. (eds.) The traveling salesman problem and its applications, pp. 585\u2013608. Kluwer Academic Publishers, Dordrecht (2002)"},{"issue":"1","key":"1769_CR5","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"issue":"4","key":"1769_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.jcss.2005.12.001","volume":"72","author":"L Engebretsen","year":"2006","unstructured":"Engebretsen, L., Karpinski, M.: TSP with bounded metrics. J. Comp. Syst. Sci. 72(4), 509\u2013546 (2006)","journal-title":"J. Comp. Syst. Sci."},{"key":"1769_CR7","unstructured":"Fekete, S.P.: Simplicity and hardness of the maximum traveling salesman problem under geometric distances. In: Proceedings 10th ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a01999), pp. 337\u2013345 (2015)"},{"key":"1769_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings 15th ACM Symposium on Theory of Computing (STOC\u00a01983), pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"issue":"1","key":"1769_CR9","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Indust. Appl. Math."},{"issue":"4","key":"1769_CR10","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602\u2013626 (2005)","journal-title":"J. ACM"},{"key":"1769_CR11","first-page":"55","volume":"26","author":"AV Kostochka","year":"1985","unstructured":"Kostochka, A.V., Serdyukov, A.I.: Polynomial algorithms with the estimates $$3\/4$$ and $$5\/6$$ for the traveling salesman problem of the maximum (in Russian). Upravlyaemye Sistemy 26, 55\u201359 (1985)","journal-title":"Upravlyaemye Sistemy"},{"issue":"47\u201349","key":"1769_CR12","doi-asserted-by":"publisher","first-page":"5000","DOI":"10.1016\/j.tcs.2009.07.051","volume":"410","author":"L Kowalik","year":"2009","unstructured":"Kowalik, L., Mucha, M.: Deterministic $$7\/8$$-approximation for the metric maximum TSP. Theor. Comp. Sci. 410(47\u201349), 5000\u20135009 (2009)","journal-title":"Theor. Comp. Sci."},{"issue":"2","key":"1769_CR13","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/s00453-009-9306-3","volume":"59","author":"L Kowalik","year":"2011","unstructured":"Kowalik, L., Mucha, M.: $$35\/44$$-approximation for asymmetric maximum TSP with triangle inequality. Algorithmica 59(2), 240\u2013255 (2011)","journal-title":"Algorithmica"},{"issue":"4","key":"1769_CR14","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, $$k$$-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"1769_CR15","doi-asserted-by":"crossref","unstructured":"Paluch, K., Mucha, M., Ma\u0327dry, A.: A $$7\/9$$-approximation algorithm for the maximum traveling salesman problem. In: Proceedings 12th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u00a02009), Lecture Notes in Computer Science, vol.\u00a05687, 298\u2013311 (2009)","DOI":"10.1007\/978-3-642-03685-9_23"},{"issue":"3","key":"1769_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theor. Comp. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comp. Sci."},{"issue":"1","key":"1769_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1769_CR18","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM 23(3), 555\u2013565 (1976)","journal-title":"J. ACM"},{"key":"1769_CR19","first-page":"79","volume":"27","author":"AI Serdyukov","year":"1987","unstructured":"Serdyukov, A.I.: An asymptotically exact algorithm for the traveling salesman problem for a maximum in Euclidean space (in Russian). Upravlyaemye sistemy 27, 79\u201387 (1987)","journal-title":"Upravlyaemye sistemy"},{"key":"1769_CR20","unstructured":"Serdyukov, A.I.: Polynomial time algorithm with estimates of accuracy of solutions for one class of the maximum cost TSP (in Russian). In: Kombinatorno-Algebraicheskie Metody v Diskretnoi Optimizatsii, pp.\u00a0107\u2013114. Nizhny Novgorod Univ., Nizhny Novgorod (1991)"},{"key":"1769_CR21","first-page":"233","volume-title":"Operations research and discrete analysis. Mathematics and its applications","author":"AI Serdyukov","year":"1997","unstructured":"Serdyukov, A.I.: The maximum-weight traveling salesman problem in finite-dimensional real spaces. In: Operations research and discrete analysis. Mathematics and its applications, vol. 391, pp. 233\u2013239. Kluwer Academic Publishers, Dordrecht (1997)"},{"issue":"2","key":"1769_CR22","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1134\/S1990478911020177","volume":"5","author":"VV Shenmaier","year":"2011","unstructured":"Shenmaier, V.V.: An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space. J. Appl. Industr. Math. 5(2), 296\u2013300 (2011)","journal-title":"J. Appl. Industr. Math."},{"issue":"2","key":"1769_CR23","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.dam.2012.09.007","volume":"163","author":"VV Shenmaier","year":"2014","unstructured":"Shenmaier, V.V.: Asymptotically optimal algorithms for geometric Max TSP and Max $$m$$-PSP. Discrete Appl. Math. 163(2), 214\u2013219 (2014)","journal-title":"Discrete Appl. Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01769-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01769-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01769-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T12:14:19Z","timestamp":1659615259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01769-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,16]]},"references-count":23,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1769"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01769-2","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,16]]},"assertion":[{"value":"7 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}