### 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 language | English |
---|---|

Title of host publication | Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers |

Editors | WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman |

Publisher | Springer-Verlag GmbH and Co. KG |

Pages | 304-312 |

Number of pages | 9 |

ISBN (Print) | 9783319730127 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation Duration: 27 Jul 2017 → 29 Jul 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10716 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 |
---|---|

Country | Russian Federation |

City | Moscow |

Period | 27.07.2017 → 29.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

*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