{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:58:27Z","timestamp":1742954307526,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319730127"},{"type":"electronic","value":"9783319730134"}],"license":[{"start":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T00:00:00Z","timestamp":1513814400000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-73013-4_28","type":"book-chapter","created":{"date-parts":[[2017,12,20]],"date-time":"2017-12-20T19:19:27Z","timestamp":1513797567000},"page":"304-312","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem"],"prefix":"10.1007","author":[{"given":"Edward Kh.","family":"Gimadi","sequence":"first","affiliation":[]},{"given":"Oxana Yu.","family":"Tsidulko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,21]]},"reference":[{"issue":"2","key":"28_CR1","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1134\/S1990478907020020","volume":"1","author":"AA Ageev","year":"2007","unstructured":"Ageev, A.A., Baburin, A.E., Gimadi, E.K.: A 3\/4 approximation algorithms for finding two disjoint Hamiltonian cycles of maximum weight. J. Appl. Indust. Math. 1(2), 142\u2013147 (2007)","journal-title":"J. Appl. Indust. Math."},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D Angluin","year":"1979","unstructured":"Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comp. Syst. Sci. 18(2), 155\u2013193 (1979)","journal-title":"J. Comp. Syst. Sci."},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1134\/S0081543811020015","volume":"272","author":"AE Baburin","year":"2011","unstructured":"Baburin, A.E., Gimadi, E.K.: On the asymptotic optimality of an algorithm for solving the maximum $$m$$-PSP in a multidimensional euclidean space. Proc. Steklov Inst. Math. 272(1), 1\u201313 (2011)","journal-title":"Proc. Steklov Inst. Math."},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02579321","volume":"7","author":"B Bollob\u00e1s","year":"1987","unstructured":"Bollob\u00e1s, B., Fenner, T.I., Frieze, A.M.: An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica 7, 327\u2013341 (1987)","journal-title":"Combinatorica"},{"key":"28_CR5","first-page":"919","volume":"7","author":"S Climer","year":"2006","unstructured":"Climer, S., Zhang, W.: Rearrangement clustering: pitfalls, remedies, and applications. JMLR 7, 919\u2013943 (2006)","journal-title":"JMLR"},{"issue":"4","key":"28_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1080\/02331939208843770","volume":"23","author":"JBJM De Kort","year":"1992","unstructured":"De Kort, J.B.J.M.: Upper bounds and lower bounds for the symmetric K-Peripatetic Salesman Problem. Optimization 23(4), 357\u2013367 (1992)","journal-title":"Optimization"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0377-2217(93)90041-K","volume":"70","author":"JBJM De Kort","year":"1993","unstructured":"De Kort, J.B.J.M.: A branch and bound algorithm for symmetric 2-Peripatetic Salesman Problems. Eur. J. Oper. Res. 70, 229\u2013243 (1993)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"28_CR8","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1287\/opre.1070.0387","volume":"55","author":"E Duchenne","year":"2007","unstructured":"Duchenne, E., Laporte, G., Semet, F.: The undirected m-Peripatetic Salesman Problem: polyhedral results and new algorithms. J. Oper. Res. 55(5), 949\u2013965 (2007)","journal-title":"J. Oper. Res."},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs I. Publ. Math. Debrecen 6, 290\u2013297 (1959)","journal-title":"Publ. Math. Debrecen"},{"issue":"2","key":"28_CR10","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1134\/S1990478914020070","volume":"8","author":"EK Gimadi","year":"2014","unstructured":"Gimadi, E.K., Glazkov, Y.V., Tsidulko, O.Y.: The probabilistic analysis of an algorithm for solving the m-planar 3-dimensional assignment problem on one-cycle permutations. J. Appl. Ind. Math. 8(2), 208\u2013217 (2014)","journal-title":"J. Appl. Ind. Math."},{"key":"28_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-319-44914-2_11","volume-title":"Discrete Optimization and Operations Research","author":"EK Gimadi","year":"2016","unstructured":"Gimadi, E.K., Istomin, A.M., Tsidulko, O.Y.: On asymptotically optimal approach to the m-Peripatetic Salesman Problem on random inputs. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 136\u2013147. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44914-2_11"},{"issue":"3","key":"28_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1134\/S1990478912030040","volume":"6","author":"EK Gimadi","year":"2012","unstructured":"Gimadi, E.K., Ivonina, E.V.: Approximation algorithms for the maximum 2-Peripatetic Salesman Problem. J. Appl. Ind. Math. 6(3), 295\u2013305 (2012)","journal-title":"J. Appl. Ind. Math."},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-319-44914-2_13","volume-title":"Discrete Optimization and Operations Research","author":"AN Glebov","year":"2016","unstructured":"Glebov, A.N., Gordeeva, A.V.: An algorithm with approximation ratio 5\/6 for\u00a0the metric maximum m-PSP. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 159\u2013170. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44914-2_13"},{"issue":"1","key":"28_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1134\/S1990478912010085","volume":"6","author":"AN Glebov","year":"2012","unstructured":"Glebov, A.N., Zambalaeva, D.Z.: A polynomial algorithm with approximation ratio 7\/9 for the maximum two Peripatetic Salesmen Problem. J. Appl. Ind. Math. 6(1), 69\u201389 (2012)","journal-title":"J. Appl. Ind. Math."},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Krishnan, S., Chhugani, J., Kumar, S., Venkatasubramanian, S.: Compressing large boolean matrices using reordering techniques. In: 30th International Conference on Very Large Databases (VLDB), pp. 13\u201323 (2004)","DOI":"10.1016\/B978-012088469-8.50005-X"},{"issue":"3","key":"28_CR16","first-page":"9","volume":"1","author":"O Johnson","year":"2006","unstructured":"Johnson, O., Liu, J.: A traveling salesman approach for predicting protein functions. Source Code Biol. Med. 1(3), 9\u201316 (2006)","journal-title":"Source Code Biol. Med."},{"issue":"4","key":"28_CR17","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":"28_CR18","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0012-365X(83)90021-3","volume":"43","author":"J Komlos","year":"1983","unstructured":"Komlos, J., Szemeredi, E.: Limit distributions for the existence of Hamilton circuits in a random graph. Discrete Math. 43, 55\u201363 (1983)","journal-title":"Discrete Math."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Krarup, J.: The Peripatetic Salesman and some related unsolved problems. In: Combinatorial Programming, Methods and Applications, pp. 173\u2013178. Reidel, Dordrecht (1975)","DOI":"10.1007\/978-94-011-7557-9_8"},{"key":"28_CR20","series-title":"Sequences of Independent Random Variables","volume-title":"Limit Theorems of Probability Theory","author":"VV Petrov","year":"1995","unstructured":"Petrov, V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Clarendon Press, Oxford (1995)"},{"issue":"5","key":"28_CR21","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1007\/s12038-007-0101-5","volume":"32","author":"SS Ray","year":"2007","unstructured":"Ray, S.S., Bandyopadhyay, S., Pal, S.K.: Gene ordering in partitive clustering using microarray expressions. J. Biosci. 32(5), 1019\u20131025 (2007)","journal-title":"J. Biosci."},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"Song, L., Zhang, Yu., Peng, X., Wang, Z., Gildea, D.: AMR-to-text generation as a Traveling Salesman Problem. In: Proceedings of 2016 Conference on Empirical Methods in Natural Language Processing (2016)","DOI":"10.18653\/v1\/D16-1224"}],"container-title":["Lecture Notes in Computer Science","Analysis of Images, Social Networks and Texts"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73013-4_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:14:56Z","timestamp":1710324896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-73013-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,21]]},"ISBN":["9783319730127","9783319730134"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73013-4_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,21]]},"assertion":[{"value":"21 December 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIST","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Analysis of Images, Social Networks and Texts","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","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":"27 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aist2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/aistconf.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}