{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:41:20Z","timestamp":1773816080910,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T00:00:00Z","timestamp":1553731200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["14-11-00109"],"award-info":[{"award-number":["14-11-00109"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s10472-019-09626-w","type":"journal-article","created":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T05:48:57Z","timestamp":1553752137000},"page":"53-69","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3555-0080","authenticated-orcid":false,"given":"Michael","family":"Khachay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katherine","family":"Neznakhina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,28]]},"reference":[{"issue":"3","key":"9626_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"EM Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994). \nhttps:\/\/doi.org\/10.1016\/0166-218X(94)90008-6","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9626_CR2","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). \nhttps:\/\/doi.org\/10.1145\/290179.290180","journal-title":"J. ACM"},{"key":"9626_CR3","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1023\/A:1018939709890","volume":"86","author":"E Balas","year":"1999","unstructured":"Balas, E.: New classes of efficiently solvable generalized traveling salesman problems. Ann. Oper. Res. 86, 529\u2013558 (1999)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"9626_CR4","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1287\/ijoc.13.1.56.9748 https:\/\/doi.org\/10.1287\/ijoc.13.1.56.9748","volume":"13","author":"E Balas","year":"2001","unstructured":"Balas, E., Simonetti, N.: Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. Comput. 13 (1), 56\u201375 (2001). \nhttps:\/\/doi.org\/10.1287\/ijoc.13.1.56.9748","journal-title":"INFORMS J. Comput."},{"key":"9626_CR5","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-319-26626-8_9","volume-title":"Combinatorial Optimization and Applications","author":"Binay Bhattacharya","year":"2015","unstructured":"Bhattacharya, B., \u0106usti\u0107, A., Rafiey, A., Rafiey, A., Sokol, V.: Approximation Algorithms for Generalized MST and TSP in Grid Clusters, Lecture Notes in Computer Science, vol. 9486, pp 110\u2013125. Springer International Publishing, Cham (2015)"},{"issue":"12","key":"9626_CR6","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.ifacol.2016.07.767","volume":"49","author":"A Chentsov","year":"2016","unstructured":"Chentsov, A., Khachay, M., Khachay, D.: Linear time algorithm for precedence constrained asymmetric generalized traveling salesman problem. IFAC-PapersOnLine 49 (12), 651\u2013655 (2016). \nhttps:\/\/doi.org\/10.1016\/j.ifacol.2016.07.767\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S2405896316310485\n\n. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016","journal-title":"IFAC-PapersOnLine"},{"issue":"1","key":"9626_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1134\/S0081543816090054","volume":"295","author":"AG Chentsov","year":"2016","unstructured":"Chentsov, A.G., Khachai, M.Y., Khachai, D.M.: An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Instit. Math. 295(1), 38\u201346 (2016). \nhttps:\/\/doi.org\/10.1134\/S0081543816090054","journal-title":"Proc. Steklov Instit. Math."},{"key":"9626_CR8","unstructured":"Cook, W.: Concorde TSP solver. \nhttp:\/\/www.math.uwaterloo.ca\/tsp\/con\\discretionary-cor\\discretionary-de.html\n\n (2003)"},{"issue":"4","key":"9626_CR9","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1137\/050636589","volume":"21","author":"M Dror","year":"2008","unstructured":"Dror, M., Orlin, J.B.: Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Discret. Math. 21(4), 1019\u20131034 (2008). \nhttps:\/\/doi.org\/10.1137\/050636589","journal-title":"SIAM J. Discret. Math."},{"key":"9626_CR10","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for tsp with neighborhoods in the plane. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201901, pp 38\u201346. Society for Industrial and Applied Mathematics, Philadelphia (2001). \nhttp:\/\/dl.acm.org\/citation.cfm?id=365411.365417"},{"issue":"3","key":"9626_CR11","doi-asserted-by":"publisher","first-page":"43,1","DOI":"10.1145\/2850418","volume":"12","author":"A Dumitrescu","year":"2016","unstructured":"Dumitrescu, A., T\u00f3th, C. D.: The traveling salesman problem for lines, balls, and planes. ACM Trans. Algor. 12(3), 43,1\u201343,29 (2016). \nhttps:\/\/doi.org\/10.1145\/2850418","journal-title":"ACM Trans. Algor."},{"issue":"2","key":"9626_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0218195909002897","volume":"19","author":"K Elbassioni","year":"2009","unstructured":"Elbassioni, K., Fishkin, A., Sitters, R.: Approximation algorithms for the euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geom. Appl. 19(2), 173\u2013193 (2009). \nhttps:\/\/doi.org\/10.1142\/S0218195909002897","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9626_CR13","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10288-006-0012-6","volume":"4","author":"C Feremans","year":"2006","unstructured":"Feremans, C., Grigoriev, A., Sitters, R.: The geometric generalized minimum spanning tree problem with grid clustering. 4OR 4(4), 319\u2013329 (2006). \nhttps:\/\/doi.org\/10.1007\/s10288-006-0012-6","journal-title":"4OR"},{"issue":"3","key":"9626_CR14","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.45.3.378","volume":"45","author":"M Fischetti","year":"1997","unstructured":"Fischetti, M., Gonz\u00e1lez, J.J.S., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45(3), 378\u2013394 (1997). \nhttps:\/\/doi.org\/10.1287\/opre.45.3.378","journal-title":"Oper. Res."},{"key":"9626_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/b101971","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Boston (2007)"},{"issue":"4","key":"9626_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985). \nhttps:\/\/doi.org\/10.1287\/moor.10.4.527","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9626_CR17","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1134\/S0081543815050107 https:\/\/doi.org\/10.1134\/S0081543815050107","volume":"289","author":"M Khachai","year":"2015","unstructured":"Khachai, M., Neznakhina, E.: A polynomial-time approximation scheme for the euclidean problem on a cycle cover of a graph. Proc. Steklov Instit. Math. 289(1), 111\u2013125 (2015). \nhttps:\/\/doi.org\/10.1134\/S0081543815050107","journal-title":"Proc. Steklov Instit. Math."},{"issue":"1","key":"9626_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1134\/S0081543817090127","volume":"299","author":"MY Khachai","year":"2017","unstructured":"Khachai, M.Y., Neznakhina, E.D.: Approximation schemes for the generalized traveling salesman problem. Proc. Steklov Instit. Math. 299(1), 97\u2013105 (2017). \nhttps:\/\/doi.org\/10.1134\/S0081543817090127","journal-title":"Proc. Steklov Instit. Math."},{"issue":"1","key":"9626_CR19","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10898-015-0391-3","volume":"66","author":"M Khachay","year":"2016","unstructured":"Khachay, M., Neznakhina, K.: Approximability of the minimum-weight k-size cycle cover problem. J. Glob. Optim. 66(1), 65\u201382 (2016). \nhttps:\/\/doi.org\/10.1007\/s10898-015-0391-3","journal-title":"J. Glob. Optim."},{"key":"9626_CR20","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-319-73013-4_32","volume-title":"Lecture Notes in Computer Science","author":"Michael Khachay","year":"2017","unstructured":"Khachay, M., Neznakhina, K.: Polynomial Time Solvable Subclass of the Generalized Traveling Salesman Problem on Grid Clusters, Lecture Notes in Computer Science, vol. 10716, pp 346\u2013355. Springer International Publishing, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-73013-4_32"},{"key":"9626_CR21","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-93800-4_6","volume-title":"Communications in Computer and Information Science","author":"Michael Khachay","year":"2018","unstructured":"Khachay, M., Neznakhina, K.: Towards tractability of the Euclidean generalized traveling salesman problem in grid clusters defined by a grid of bounded height. In: Communications in Computer and Information Science, vol. 871, pp 68\u201377. Springer International Publishing, Cham (2018), \nhttps:\/\/doi.org\/10.1007\/978-3-319-93800-4_6"},{"key":"9626_CR22","doi-asserted-by":"crossref","unstructured":"McQuarrie, A.D.R., Tsai, C.L.: Regression and Time Series Model Selection. World Scientific (1998)","DOI":"10.1142\/3573"},{"issue":"4","key":"9626_CR23","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JS Mitchell","year":"1999","unstructured":"Mitchell, J.S.: 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). \nhttps:\/\/doi.org\/10.1137\/S0097539796309764","journal-title":"SIAM J. Comput."},{"key":"9626_CR24","unstructured":"Mitchell, J.S.B.: A ptas for tsp with neighborhoods among fat regions in the plane. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907. \nhttp:\/\/dl.acm.org\/citation.cfm?id=1283383.1283385\n\n, pp 11\u201318. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"key":"9626_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.: Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237\u2013244 (1977)","journal-title":"Theoret. Comput. Sci."},{"key":"9626_CR26","unstructured":"Weisberg, S.: Applied Linear Regression, 4 edn. Wiley (2013)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09626-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-019-09626-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09626-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,27]],"date-time":"2020-03-27T00:22:05Z","timestamp":1585268525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-019-09626-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,28]]},"references-count":26,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["9626"],"URL":"https:\/\/doi.org\/10.1007\/s10472-019-09626-w","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,28]]},"assertion":[{"value":"28 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}