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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы283-293
Число страниц11
ISBN (печатное издание)9783030110260
DOI
СостояниеОпубликовано - 1 янв 2018
Событие7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 - Moscow, Российская Федерация
Продолжительность: 5 июл 20187 июл 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11179 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
СтранаРоссийская Федерация
ГородMoscow
Период05.07.201807.07.2018

Fingerprint Подробные сведения о темах исследования «On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

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