Asymptotically optimal algorithm for the maximum M-peripatetic salesman problem in a normed space

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

1 Citation (Scopus)

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 languageEnglish
Title of host publicationLearning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages402-410
Number of pages9
ISBN (Print)9783030053475
DOIs
Publication statusPublished - 1 Jan 2019
Event12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Greece
Duration: 10 Jun 201815 Jun 2018

Publication series

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

Conference

Conference12th International Conference on Learning and Intelligent Optimization, LION 12
CountryGreece
CityKalamata
Period10.06.201815.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