{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:50:34Z","timestamp":1743141034335,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319711492"},{"type":"electronic","value":"9783319711508"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-71150-8_23","type":"book-chapter","created":{"date-parts":[[2017,11,16]],"date-time":"2017-11-16T00:48:21Z","timestamp":1510793301000},"page":"265-277","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem"],"prefix":"10.1007","author":[{"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":[[2017,11,17]]},"reference":[{"key":"23_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, 753\u2013783 (1998)","journal-title":"J. ACM"},{"issue":"9","key":"23_CR2","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1016\/j.dam.2008.06.025","volume":"157","author":"A Baburin","year":"2009","unstructured":"Baburin, A., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.T.: Approximation algorithms for the 2-Peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157(9), 1988\u20131992 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"23_CR3","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/j.orl.2005.12.001","volume":"34","author":"MF Baki","year":"2006","unstructured":"Baki, M.F.: A new asymmetric pyramidally solvable class of the traveling salesman problem. Oper. Res. Lett. 34(6), 613\u2013620 (2006). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167637706000022","journal-title":"Oper. Res. Lett."},{"key":"23_CR4","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":"23_CR5","doi-asserted-by":"publisher","first-page":"56","DOI":"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). https:\/\/doi.org\/10.1287\/ijoc.13.1.56.9748","journal-title":"INFORMS J. Comput."},{"key":"23_CR6","unstructured":"de Berg, M., Buchin, K., Jansen, B.M.P., Woeginger, G.: Fine-grained complexity analysis of two classic TSP Variants. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 5:1\u20135:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/6277"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Burkard, R.E., Glazkov, Y.V.: On the traveling salesman problem with a relaxed monge matrix. Inform. Process. Lett. 67(5), 231\u2013237 (1998). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019098001197","DOI":"10.1016\/S0020-0190(98)00119-7"},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev. 40(3), 496\u2013546 (1998)","journal-title":"SIAM Rev."},{"issue":"1","key":"23_CR9","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 Ins. Math. 295(1), 38\u201346 (2016). https:\/\/doi.org\/10.1134\/S0081543816090054","journal-title":"Proc. Steklov Ins. Math."},{"key":"23_CR10","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the Traveling Salesman Problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)"},{"issue":"1\u20133","key":"23_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0166-218X(98)00048-1","volume":"87","author":"H Enomoto","year":"1998","unstructured":"Enomoto, H., Oda, Y., Ota, K.: Pyramidal tours with step-backs and the asymmetric Traveling Salesman Problem. Discrete Appl. Math. 87(1\u20133), 57\u201365 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"23_CR12","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1134\/S1990478914020070","volume":"8","author":"EK Gimadi","year":"2014","unstructured":"Gimadi, E.K., Glazkov, Y., Tsidulko, O.Y.: Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations. J. Appl. Ind. Math. 8(2), 208\u2013217 (2014)","journal-title":"J. Appl. Ind. Math."},{"issue":"1","key":"23_CR13","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1134\/S1064562416010233","volume":"93","author":"EK Gimadi","year":"2016","unstructured":"Gimadi, E.K., Rykov, I.A.: On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math. 93(1), 117\u2013120 (2016)","journal-title":"Dokl. Math."},{"key":"23_CR14","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":"2","key":"23_CR15","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1134\/S1064562415020313","volume":"91","author":"M Khachai","year":"2015","unstructured":"Khachai, M., Neznakhina, E.: Approximability of the problem about a minimum-weight cycle cover of a graph. Doklady Math. 91(2), 240\u2013245 (2015)","journal-title":"Doklady Math."},{"issue":"1","key":"23_CR16","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). https:\/\/doi.org\/10.1007\/s10898-015-0391-3","journal-title":"J. Glob. Optim."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"050003","DOI":"10.1063\/1.4965324","volume":"1776","author":"M Khachay","year":"2016","unstructured":"Khachay, M., Neznakhina, K.: Towards a PTAS for the generalized TSP in grid clusters. AIP Conf. Proc. 1776(1), 050003 (2016). https:\/\/doi.org\/10.1063\/1.4965324","journal-title":"AIP Conf. Proc."},{"key":"23_CR18","unstructured":"Klyaus, P.: Generation of testproblems for the Traveling Salesman Problem. Preprint Inst. Mat. Akad. Nauk. BSSR (16) (1976). (in Russian)"},{"key":"23_CR19","series-title":"Wiley Series in Discrete Mathematics & Optimization","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"EL Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics & Optimization. Wiley, Chichester (1985)"},{"issue":"1","key":"23_CR20","first-page":"123","volume":"7","author":"Y Oda","year":"2001","unstructured":"Oda, Y., Ota, K.: Algorithmic aspects of pyramidal tours with restricted jump-backs. Interdisc. Inform. Sci. 7(1), 123\u2013133 (2001)","journal-title":"Interdisc. Inform. Sci."},{"key":"23_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1","volume-title":"Handbook of Combinatorial Optimization","author":"P Pardalos","year":"2013","unstructured":"Pardalos, P., Du, D., Graham, R.: Handbook of Combinatorial Optimization. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4419-7997-1"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzales, T.: P-complete approximation problems. J. ACM 23, 555\u2013565 (1976)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71150-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T13:46:36Z","timestamp":1709819196000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-71150-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319711492","9783319711508"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71150-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"17 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/anl.sjtu.edu.cn\/cocoa2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}