On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem

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

1 Citation (Scopus)

Abstract

The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptotically optimal algorithm for the Euclidean maximum TSP with running-time O(n3), that uses a maximum weight cycle cover of the initial graph as a foundation for constructing the TSP solution. We also prove a number of structural results for the optima of some maximization problems in normed spaces, which follow from the algorithm.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages283-293
Number of pages11
ISBN (Print)9783030110260
DOIs
Publication statusPublished - 1 Jan 2018
Event7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 - Moscow, Russian Federation
Duration: 5 Jul 20187 Jul 2018

Publication series

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

Conference

Conference7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
CountryRussian Federation
CityMoscow
Period05.07.201807.07.2018

Keywords

  • Asymptotically optimal algorithm
  • Cycle cover
  • Euclidean space
  • Maximum traveling salesman problem
  • Metric space
  • Normed space

Fingerprint Dive into the research topics of 'On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem'. Together they form a unique fingerprint.

  • Cite this

    Gimadi, E. K., & Tsidulko, O. Y. (2018). On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. In Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (pp. 283-293). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-11027-7_27