@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",
}