@inproceedings{f1ddfd152b974729ba551cefc61a2f67,

title = "Approximation algorithms for the maximum m-peripatetic salesman problem",

abstract = "We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a, b] these algorithms are asymptotically optimal for m= o(n). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.",

keywords = "Edge-disjoint Hamiltonian cycles, Maximum m-Peripatetic salesman problem, Time complexity, Maximum m-Peripatetic Salesman Problem, CYCLES",

author = "Gimadi, {Edward Kh} and Tsidulko, {Oxana Yu}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-73013-4_28",

language = "English",

isbn = "9783319730127",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "304--312",

editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",

booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",

address = "Germany",

note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",

}