### Abstract

The maximum m-Peripatetic Salesman Problem (m-PSP) consists of determining m edge-disjoint Hamiltonian cycles of maximum total weight in a given complete weighted n-vertex graph. We consider a geometric variant of the problem and describe a polynomial time approximation algorithm for the m-PSP in a normed space of fixed dimension. We prove that the algorithm is asymptotically optimal for m = o(n).

Original language | English |
---|---|

Title of host publication | Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers |

Publisher | Springer-Verlag GmbH and Co. KG |

Pages | 402-410 |

Number of pages | 9 |

ISBN (Print) | 9783030053475 |

DOIs | |

Publication status | Published - 1 Jan 2019 |

Event | 12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Greece Duration: 10 Jun 2018 → 15 Jun 2018 |

### Publication series

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

Volume | 11353 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 12th International Conference on Learning and Intelligent Optimization, LION 12 |
---|---|

Country | Greece |

City | Kalamata |

Period | 10.06.2018 → 15.06.2018 |

### Keywords

- Asymptotically optimal algorithm
- Maximum m-peripatetic salesman problem
- Maximum traveling salesman problem
- Normed space

## Fingerprint Dive into the research topics of 'Asymptotically optimal algorithm for the maximum M-peripatetic salesman problem in a normed space'. Together they form a unique fingerprint.

## Cite this

Gimadi, E. K., & Tsidulko, O. Y. (2019). Asymptotically optimal algorithm for the maximum M-peripatetic salesman problem in a normed space. In

*Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers*(pp. 402-410). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11353 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-05348-2_33