{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:46:44Z","timestamp":1767016004672},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319449135"},{"type":"electronic","value":"9783319449142"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44914-2_11","type":"book-chapter","created":{"date-parts":[[2016,11,29]],"date-time":"2016-11-29T21:56:02Z","timestamp":1480456562000},"page":"136-147","source":"Crossref","is-referenced-by-count":3,"title":["On Asymptotically Optimal Approach to the m-Peripatetic Salesman Problem on Random Inputs"],"prefix":"10.1007","author":[{"given":"Edward Kh.","family":"Gimadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexey M.","family":"Istomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oxana Yu.","family":"Tsidulko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"issue":"2","key":"11_CR1","doi-asserted-by":"crossref","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. Ind. Math. 1(2), 142\u2013147 (2007)","journal-title":"J. Appl. Ind. Math."},{"issue":"4","key":"11_CR2","first-page":"3","volume":"16","author":"AA Ageev","year":"2009","unstructured":"Ageev, A.A., Pyatkin, A.V.: A 2-approximation algorithm for the metric 2-peripatetic salesman problem. Diskretn. Anal. Issled. Oper. 16(4), 3\u201320 (2009)","journal-title":"Diskretn. Anal. Issled. Oper."},{"issue":"2","key":"11_CR3","doi-asserted-by":"crossref","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. Comput. Syst. Sci. 18(2), 155\u2013193 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"11_CR4","doi-asserted-by":"crossref","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."},{"issue":"11","key":"11_CR5","first-page":"11","volume":"2","author":"AE Baburin","year":"2004","unstructured":"Baburin, A.E., Gimadi, E.K., Korkishko, N.M.: Approximation algorithms for finding two edge-disjoint Hamiltonian cycles of minimal total weight (in Russian). J. Discr. Anal. Oper. Res. 2(11), 11\u201325 (2004)","journal-title":"J. Discr. Anal. Oper. Res."},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF02579321","volume":"7","author":"B Bollobas","year":"1987","unstructured":"Bollobas, 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":"11_CR7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1734213.1734218","volume":"57","author":"P Chebolu","year":"2010","unstructured":"Chebolu, P., Frieze, A.M., Melsted, P.: Finding a maximum matching in a sparse random graph in O(n) expected time. JACM 57, 24 (2010)","journal-title":"JACM"},{"issue":"3","key":"11_CR8","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1080\/02331939708844286","volume":"39","author":"MJD Brey De","year":"1997","unstructured":"De Brey, M.J.D., Volgenant, A.: Well-solved cases of the 2-peripatetic salesman problem. Optimization 39(3), 275\u2013293 (1997)","journal-title":"Optimization"},{"issue":"4","key":"11_CR9","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1080\/02331939208843770","volume":"23","author":"JBJM Kort De","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"},{"issue":"1","key":"11_CR10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/02331939108843650","volume":"22","author":"JBJM DeKort","year":"1991","unstructured":"DeKort, J.B.J.M.: Lower bounds for symmetric K-peripatetic salesman problems. Optimization 22(1), 113\u2013122 (1991)","journal-title":"Optimization"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0377-2217(93)90041-K","volume":"70","author":"JBJM Kort De","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."},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erdos","year":"1959","unstructured":"Erdos, P., Renyi, A.: On random graphs I. Publ. Math. Debrecen 6, 290\u2013297 (1959)","journal-title":"Publ. Math. Debrecen"},{"issue":"1","key":"11_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/rsa.20542","volume":"47","author":"A Frieze","year":"2015","unstructured":"Frieze, A., Haber, S.: An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three. J. Random Struct. Algorithms 47(1), 73\u201398 (2015)","journal-title":"J. Random Struct. Algorithms"},{"issue":"1","key":"11_CR14","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1134\/S1990478909010074","volume":"3","author":"EK Gimadi","year":"2009","unstructured":"Gimadi, E.K., Glazkov, Y.V., Glebov, A.N.: Approximation algorithms for sollving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2. J. Appl. Ind. Math. 3(1), 46\u201360 (2009)","journal-title":"J. Appl. Ind. Math."},{"issue":"2","key":"11_CR15","doi-asserted-by":"crossref","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."},{"issue":"11","key":"11_CR16","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.dam.2015.03.007","volume":"196","author":"EK Gimadi","year":"2015","unstructured":"Gimadi, E.K., Glebov, A.N., Skretneva, A.A., Tsidulko, O.Y., Zambalaeva, D.Z.: Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph. Discrete Appl. Math. 196(11), 54\u201361 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"11_CR17","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1134\/S0081543815050077","volume":"289","author":"EK Gimadi","year":"2015","unstructured":"Gimadi, E.K., Istomin, A.M., Rykov, I.A., Tsidulko, O.Y.: Probabilistic analysis of an approximation algorithm for the m-peripatetic salesman problem on random instances unbounded from above. Proc. Steklov Inst. Math. 289(1), 77\u201387 (2015)","journal-title":"Proc. Steklov Inst. Math."},{"issue":"3","key":"11_CR18","doi-asserted-by":"crossref","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":"11_CR19","first-page":"15","volume":"22","author":"EK Gimadi","year":"1973","unstructured":"Gimadi, E.K., Perepelitsa, V.A.: A statistically effective algorithm for the selection of a Hamiltonian contour or cycle (in Russian). J. Diskret. Anal. 22, 15\u201328 (1973)","journal-title":"J. Diskret. Anal."},{"issue":"1","key":"11_CR20","doi-asserted-by":"crossref","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."},{"issue":"2","key":"11_CR21","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1134\/S1990478912020056","volume":"6","author":"AN Glebov","year":"2012","unstructured":"Glebov, A.N., Zambalaeva, D.Z.: An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions. J. Appl. Ind. Math. 6(2), 167\u2013183 (2012)","journal-title":"J. Appl. Ind. Math."},{"key":"11_CR22","doi-asserted-by":"crossref","first-page":"5563","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, 5563 (1983)","journal-title":"Discrete Math."},{"key":"11_CR23","first-page":"1100","volume":"11","author":"AD Korshunov","year":"1970","unstructured":"Korshunov, A.D.: On the power of some classes of graphs. Sov. Math. Dokl. 11, 1100\u20131104 (1970)","journal-title":"Sov. Math. Dokl."},{"key":"11_CR24","series-title":"NATO Advanced Study Institutes Series","first-page":"173","volume-title":"Combinatorial Programming, Methods and Applications","author":"J Krarup","year":"1975","unstructured":"Krarup, J.: The peripatetic salesman and some related unsolved problems. In: Roy, B. (ed.) Combinatorial Programming, Methods and Applications. NATO Advanced Study Institutes Series, vol. 19, pp. 173\u2013178. Reidel, Dordrecht (1975)"},{"key":"11_CR25","volume-title":"Limit Theorems of Probability Theory. Sequences of Independent Random Variables","author":"VV Petrov","year":"1995","unstructured":"Petrov, V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Clarendon Press, Oxford (1995)"}],"container-title":["Lecture Notes in Computer Science","Discrete Optimization and Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44914-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T03:24:39Z","timestamp":1692588279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44914-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449135","9783319449142"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44914-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}