Approximation algorithms for the maximum m-peripatetic salesman problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
EditorsWMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
PublisherSpringer-Verlag GmbH and Co. KG
Pages304-312
Number of pages9
ISBN (Print)9783319730127
DOIs
Publication statusPublished - 1 Jan 2018
Event6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation
Duration: 27 Jul 201729 Jul 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10716 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
CountryRussian Federation
CityMoscow
Period27.07.201729.07.2017

Keywords

  • Edge-disjoint Hamiltonian cycles
  • Maximum m-Peripatetic salesman problem
  • Time complexity
  • Maximum m-Peripatetic Salesman Problem
  • CYCLES

Fingerprint Dive into the research topics of 'Approximation algorithms for the maximum m-peripatetic salesman problem'. Together they form a unique fingerprint.

  • Cite this

    Gimadi, E. K., & Tsidulko, O. Y. (2018). Approximation algorithms for the maximum m-peripatetic salesman problem. In WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Eds.), Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (pp. 304-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-73013-4_28