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

Edward Kh Gimadi; Oxana Yu Tsidulko

doi:10.1007/978-3-030-11027-7_27

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(n³), 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	https://doi.org/10.1007/978-3-030-11027-7_27
Состояние	Опубликовано - 1 янв 2018
Событие	7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 - Moscow, Российская Федерация Продолжительность: 5 июл 2018 → 7 июл 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.2018 → 07.07.2018

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

Gimadi, Edward Kh ; Tsidulko, Oxana Yu. / 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. Springer-Verlag GmbH and Co. KG, 2018. стр. 283-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0502a9aa7d0f452896336078a1b10b93,

title = "On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem",

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.",

keywords = "Asymptotically optimal algorithm, Cycle cover, Euclidean space, Maximum traveling salesman problem, Metric space, Normed space",

author = "Gimadi, {Edward Kh} and Tsidulko, {Oxana Yu}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-11027-7_27",

language = "English",

isbn = "9783030110260",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "283--293",

booktitle = "Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers",

address = "Germany",

note = "7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 ; Conference date: 05-07-2018 Through 07-07-2018",

}

Gimadi, EK & Tsidulko, OY 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. 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, стр. 283-293, 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018, Moscow, Российская Федерация, 05.07.2018. https://doi.org/10.1007/978-3-030-11027-7_27

On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. / Gimadi, Edward Kh ; Tsidulko, Oxana Yu.

Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. стр. 283-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11179 LNCS).

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

TY - GEN

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

AU - Gimadi, Edward Kh

AU - Tsidulko, Oxana Yu

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Asymptotically optimal algorithm

KW - Cycle cover

KW - Euclidean space

KW - Maximum traveling salesman problem

KW - Metric space

KW - Normed space

UR - http://www.scopus.com/inward/record.url?scp=85059937588&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-11027-7_27

DO - 10.1007/978-3-030-11027-7_27

M3 - Conference contribution

AN - SCOPUS:85059937588

SN - 9783030110260

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

SP - 283

EP - 293

BT - Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018

Y2 - 5 July 2018 through 7 July 2018

ER -

Gimadi EK , Tsidulko OY. 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. Springer-Verlag GmbH and Co. KG. 2018. стр. 283-293. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-11027-7_27

Доступ к документу

10.1007/978-3-030-11027-7_27

Link to publication in Scopus